PSPACE-complete
In complexity theory, PSPACE-complete is a complexity class. A decision problem is in PSPACE-complete if it is in PSPACE, and every problem in PSPACE can be reduced to it in polynomial time. The problems in PSPACE-complete can be thought of as the hardest problems in PSPACE. These problems are widely suspected to be outside of P and NP, but that is not known. It is known that they lie outside of NC.
The first known NP-complete problem was satisfiability (SAT). This is the problem of whether there are assignments of truth values to variables that make a boolean expression true. For example, one instance of SAT would be the question of whether the following is true:
The SAT problem can be generalized to TQBF, the most basic PSPACE-complete problem. Instances of this problem are similar to SAT, except that universal quantifiers are also allowed:
Notice that the NP-complete problem resembles a typical puzzle: is there some way to plug in values that solves the problem? The PSPACE-complete problem resembles a game: 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.
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 and the solitaire games Rush Hour, mahjong, Atomix and Sokoban. 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.
Note that the definition of PSPACE-complete 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 game like checkers (which is played on an 8 × 8 board) could never be PSPACE-complete (in fact, they can be solved in constant time and space using a very large lookup table). 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 somewhat artificial and subjective.
Another PSPACE-complete problem is the problem of deciding whether a given string is a member of the language defined by a given context-sensitive grammar.
See also
References
- Michael Sipser (1997). Introduction to the Theory of Computation. PWS Publishing. ISBN 0-534-94728-X. Section 8.3: PSPACE-completeness, pp.283–294.
- Michael R. Garey and David S. Johnson (1979). Computers and Intractability: A Guide to the Theory of NP-Completeness. W.H. Freeman. ISBN 0-7167-1045-5. Section 7.4: Polynomial Space Completeness, pp.170–177.