PSPACE-complete

From Academic Kids

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:

<math>\exists x_1 \, \exists x_2 \, \exists x_3 \, \exists x_4: (x_1 \or \neg x_3 \or x_4) \and (\neg x_2 \or x_3 \or \neg x_4)<math>

The most basic PSPACE-complete problem is identical, except every other quantifier is a universal quantifier:

<math>\exists x_1 \, \forall x_2 \, \exists x_3 \, \forall x_4: (x_1 \or \neg x_3 \or x_4) \and (\neg x_2 \or x_3 \or \neg x_4)<math>

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. That is why all the games were modified by playing them on an n × n board instead.

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]