Problems known to be PSPACE-complete include determining properties of regular expressions and context-sensitive grammars, determining the truth of quantified Boolean formulas, step-by-step changes between solutions of combinatorial optimization problems, and many puzzles and games.
[2] It is known that they lie outside of the class NC, a class of problems with highly efficient parallel algorithms, because problems in NC can be solved in an amount of space polynomial in the logarithm of the input size, and the class of problems solvable in such a small amount of space is strictly contained in PSPACE by the space hierarchy theorem.
The transformations that are usually considered in defining PSPACE-completeness are polynomial-time many-one reductions, transformations that take a single instance of a problem of one type into an equivalent single instance of a problem of a different type.
It is not known whether these two types of reductions lead to different classes of PSPACE-complete problems.
In the word problem for context-sensitive grammars, one is given a set of grammatical transformations which can increase, but cannot decrease, the length of a sentence, and wishes to determine if a given sentence could be produced by these transformations.
The technical condition of "determinism" (implying roughly that each transformation makes it obvious that it was used) ensures that this process can be solved in polynomial space, and Kuroda (1964) showed that every (possibly non-deterministic) program computable in linear space could be converted into the parsing of a context-sensitive grammar, in a way which preserves determinism.
For instance, testing whether two 4-colorings of a graph can be connected to each other by moves that change the color of one vertex at a time, maintaining at each step a valid 4-coloring, is PSPACE-complete,[8] even though the same problem for 3-colorings can be solved in polynomial time.
[9] Another family of reconfiguration problems, used similarly to quantified Boolean formulas as the basis for PSPACE-completeness proofs of many other problems in this area, involve nondeterministic constraint logic, in which the states are orientations of a constraint graph subject to certain constraints on how many edges must be oriented inwards at each vertex, and in which the moves from state to state reverse the orientation of a single edge.
[10] 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.
Similarly, the problem of determining the winner or loser of many other combinatorial games turns out to be PSPACE-complete.
But they will become PSPACE-complete if a polynomial bound on the number of moves is enforced.
These often can be interpreted as reconfiguration problems,[10] and include the solitaire games Rush Hour, Mahjong, Atomix and Sokoban, and the mechanical computer Turing Tumble.
[11] PSPACE-completeness is based on complexity as a function of the input size
Puzzles or games with a bounded number of positions such as chess on a conventional
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