Editing PSPACE-complete (section)

===Puzzles and games===
{{For|a list of games by completeness for PSPACE or other complexity classes|Game complexity}}
The quantified Boolean formula problem can be interpreted as a game by two players, a verifier and a falsifier. The players make moves that fill in values for the quantified variables, in the order they are nested, with the verifier filling in existentially quantified variables and the falsifier filling in universally quantified variables; the game is won by the verifier if the filled-in formula becomes true, and by the falsifier otherwise. A quantified formula is true if and only if the verifier has a winning strategy. Similarly, the problem of determining the winner or loser of many other [[combinatorial game theory|combinatorial games]] turns out to be PSPACE-complete. Examples of games that are PSPACE-complete (when [[generalized game|generalized]] so that they can be played on an <math>n\times n</math> board) are the games [[Hex (board game)|Hex]] and [[Reversi]].  Some other generalized games, such as [[chess]], [[English draughts|checkers]] (draughts), and [[Go (board game)|Go]] are [[EXPTIME-complete]] because a game between two perfect players can be very long, so they are unlikely to be in PSPACE. But they will become PSPACE-complete if a polynomial bound on the number of moves is enforced.{{r|eppstein}}

It is also possible for puzzles played by a single player to be PSPACE-complete. These often can be interpreted as reconfiguration problems,{{r|hearn-demaine}} and include the solitaire games [[Rush Hour (board game)|Rush Hour]], [[Mahjong solitaire|Mahjong]], [[Atomix (computer game)|Atomix]] and [[Sokoban]], and the [[mechanical computer]] [[Turing Tumble]].{{r|eppstein}}

PSPACE-completeness is based on complexity as a function of the input size <math>n</math>, in the limit as <math>n</math> grows without bound. Puzzles or games with a bounded number of positions such as chess on a conventional <math>8\times 8</math> board cannot be PSPACE-complete, because they could be solved in constant time and space using a very large [[lookup table]]. To formulate PSPACE-complete versions of these games, they must be modified in a way that makes their number of positions unbounded, such as by playing them on an <math>n\times n</math> board instead. In some cases, such as for chess, these extensions are artificial.