Playing Disjunctive Sums is Polynomial Space Complete (1981)

F. Lockwood Morris

Abstract

A position in a disjunctive sum of games is simply a collection of positions, one from each game: to move in a sum is to move in any one of its constituents. Sums have been studied extensively by Conway and others, and play an important role in Go.

It is shown that the problem of best play in a sum of trivial games is polynomial space complete. Hence it may be conjectured that there is no feasible algorithm for deriving a strategy of play in a sum from knowledge about its constituent games.