Complexity of decision problems based on finite two-person perfect-information games

摘要

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.