PSPACE-complete
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:
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.
