PSPACE-complete

From Wikipedia, the free encyclopedia

This article contains too much jargon and may need simplification or further explanation. Please discuss this issue on the talk page, and/or remove or explain jargon terms used in the article. Editing help is available. (June 2009)

In complexity theory, a decision problem is PSPACE-complete if it is in the complexity class PSPACE, and every problem in PSPACE can be reduced to it in polynomial time (see complete (complexity)). 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 the more famous complexity classes P and NP, but that is not known. It is known that they lie outside of NC.

[edit] Discussion

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:

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:

.

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.

[edit] 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.

[edit] TQBF

• Let TQBF = { <F> : 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=pF', recursively evaluate F'[p=1] and F'[p=0], accept iff both accept.
  • If F=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.^[1]

[edit] Winning Strategies For Games

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

[edit] Generalized geography

• On input <G,b>:
  • If b has no outgoing edge, reject.
  • Otherwise, remove b and all its edges, call this new graph G₁.
  • Recursively run on inputs <G₁,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.^[1]

[edit] 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.

1. ^ ^{a b} François Pitt. "Lecture Summary for Week 11 work" (html). http://www.cs.utoronto.ca/~fpitt/CSC363/20079/lectures/LN11.txt. Retrieved on 2008-02-12. 

[edit] External links

• Computational Complexity of Games and Puzzles
• Go/Baduk, Board game: "Ladders" work in this way