PSPACE-complete

Given a regular expression R, determining whether it generates every string over its alphabet is PSPACE-complete.[2]

A related result is that the class of languages recognizable with zero error by automata with two-way infinite random tape equals nondeterministic linear space. This holds for both two-way and multipass one-way access to input. Testing whether an automaton (with two-way infinite random tape) accepts a word with zero error is NSPACE(O(kn)) complete, where n is the input size and k is the number of states.

The first known PSPACE-complete problem was the word problem for deterministic context-sensitive grammars. 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.[3] In 1970, Savitch's theorem showed that PSPACE is closed under nondeterminism, implying that even non-deterministic context-sensitive grammars are in PSPACE.

Nowadays, the archetypal PSPACE-complete problem is generally taken to be the quantified Boolean formula problem (usually abbreviated to QBF or TQBF; the T stands for "true"), a generalization of the first known NP-complete problem, the Boolean satisfiability problem (SAT). The satisfiability problem is the problem of whether there are assignments of truth values to variables that make a Boolean expression true.[4] For example, one instance of SAT would be the question of whether the following is true:

${\displaystyle \exists x_{1}\,\exists x_{2}\,\exists x_{3}\,\exists x_{4}:(x_{1}\lor \neg x_{3}\lor x_{4})\land (\neg x_{2}\lor x_{3}\lor \neg x_{4})}$

The quantified Boolean formula problem differs in allowing both universal and existential quantification over the values of the variables:

${\displaystyle \exists x_{1}\,\forall x_{2}\,\exists x_{3}\,\forall x_{4}:(x_{1}\lor \neg x_{3}\lor x_{4})\land (\neg x_{2}\lor x_{3}\lor \neg x_{4})}$.

The proof that QBF is a PSPACE-complete problem is essentially a restatement of the proof of Savitch's theorem in the language of logic, and is a bit more technical.

The NP-complete problem in the previous section resembles typical puzzles: is there some way to plug in values that solves the problem? Correspondingly, the PSPACE-complete problem there resembles games: is there some move I can make, such that for all moves my opponent might make, there will then be some move I can make to win? The question alternates existential and universal quantifiers. Not surprisingly, many puzzles turn out to be NP-complete, and many games turn out to be PSPACE-complete.[5]

Examples of games that are PSPACE-complete (when generalized so that they can be played on an n × n board) are the games Hex and Reversi the solitaire games Rush Hour, Mahjong, Atomix and Sokoban, and the mechanical computer Turing Tumble. Some other generalized games, such as chess, checkers (draughts), and 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.[5]

Note that the definition of PSPACE-completeness is based on asymptotic complexity: the time it takes to solve a problem of size n, in the limit as n grows without bound. That means a finite game like checkers (which is played on an 8 × 8 board) could never be PSPACE-complete, since they can be solved in constant time and space using a very large lookup table (checkers is already solved in this way). That is why all the games were modified by playing them on an n × n board instead; in some cases, such as for Chess, these extensions are artificial.