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 spacea 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.
complexity games optimality play completeness polynomial space assurance general structure informal