Encyclopedia > PSPACE-complete

  Article Content


In complexity theory, PSPACE-complete is a set of decision problems. A 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 \, \forall 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.

The game of checkers (draughts) is PSPACE-complete when played on an n × n board. So are the games of Hex, Othello, Rush Hour[?], Shanghai, and Sokoban. Other games, such as Chess and Go are more difficult (EXPTIME-complete) because a game between two perfect players can be very long.

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.

External link

All Wikipedia text is available under the terms of the GNU Free Documentation License

  Search Encyclopedia

Search over one million articles, find something about almost anything!
  Featured Article
Digital Rights Management

... freedom-to-tinker Web site for information and pointers. An early example of a DRM system is the Content Scrambling System (CSS) employed by the DVD Consortium[?] ...

This page was created in 24.3 ms