Complexity of decision problems based on finite two-person perfect-information games
Thomas J. Schaefer · 1976
We present a number of simply-structured combinatorial games for which the problem of determining the outcome of optimal play is complete in polynomial space—a condition which gives very strong assurance that these problems are hard. In addition to proving this completeness property for some particular games, we introduce a general technique for deriving games complete in polynomial space from NP-complete problems.