PSPACE-complete

Mathematicians and computer scientists try to carefully define different types of complexity, and PSPACE-complete is one of these types.Roughly, PSPACE is all the problems which can be solved by programs which only need a polynomial (in the length of the problem instance specification) amount of memory to run,and it turns out that some of these problems are essentially as hard as any such problem can be. Such problems are called PSPACE-complete.

Technical Description

In complexity theory, a decision problem is PSPACE-complete if it is in PSPACE and every problem in PSPACE can be reduced to it in polynomial time. The problems that are 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 the Boolean satisfiability problem (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:: $exists\; x\_1\; ,\; exists\; x\_2\; ,\; exists\; x\_3\; ,\; exists\; x\_4:\; (x\_1\; or\; eg\; x\_3\; or\; x\_4)\; and\; (\; eg\; x\_2\; or\; x\_3\; or\; eg\; x\_4)$

The SAT problem can be generalized to the quantified Boolean formula problem (QBF), an important PSPACE-complete problem that allows both universal and existential quantification over the values of the variables:: $exists\; x\_1\; ,\; forall\; x\_2\; ,\; exists\; x\_3\; ,\; forall\; x\_4:\; (x\_1\; or\; eg\; x\_3\; or\; x\_4)\; and\; (\; eg\; x\_2\; or\; x\_3\; or\; eg\; x\_4)$. The proof of 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.

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-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 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.

Examples of PSPACE-complete problems

Following are a few PSPACE-complete problems with outlines of the algorithms showing that they are in PSPACE. More examples can be found at list of PSPACE-complete problems.

TQBF

* Let TQBF = { : F is a true fully quantified boolean formula }. On input F:
** If F has no quantifier, evaluate and accept iff F is true.
** If F=$forall$pF', recursively evaluate F' [p=1] and F' [p=0] , accept iff both accept.
** If F=$exist$qF', recursively evaluate F' [q=1] , F' [q=0] and accept iff at least one accept.
* Space Usage: The number of levels of recursion is equal to the number of variables of F. The amount of information stored at each level of recursion is constant (values of formula for p=0 and p=1). Therefore the total space used is linear. [cite web| title = Lecture Summary for Week 11 work| author = François Pitt| url =http://www.cs.utoronto.ca/~fpitt/CSC363/20079/lectures/LN11.txt | format = html | accessdate = 2008-02-12]

Winning Strategies For Games

See Game complexity for more games whose completeness for PSPACE or other complexity classes has been determined.

Generalized geography

* On input :
** If b has no outgoing edge, reject.
** Otherwise, remove b and all its edges, call this new graph G₁.
** Recursively run on inputs 1,b_i>, where each b_i are the endpoints of edges from b.
** Reject if all accept; otherwise accept.
* Space Usage: The number of levels of recursion is equal to the number of nodes in G. The amount of information stored at each level of recursion is equal to the number of nodes in G. Therefore the total space used is linear. [cite web| title = Lecture Summary for Week 11 work| author = François Pitt| url =http://www.cs.utoronto.ca/~fpitt/CSC363/20079/lectures/LN11.txt | format = html | accessdate = 2008-02-12]

References

* Section 8.3: PSPACE-completeness, pp.283–294.
* Section 7.4: Polynomial Space Completeness, pp.170–177.

External links

* [http://www.ics.uci.edu/~eppstein/cgt/hard.html Computational Complexity of Games and Puzzles]
* [http://senseis.xmp.net/?path=Tesuji&page=Ladder Go/Baduk, Board game: "Ladders" work in this way]