The first known NPcomplete 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 most basic PSPACEcomplete problem is identical, except every other quantifier is a universal quantifier:
Notice that the NPcomplete problem resembles a typical puzzle: is there some way to plug in values that solves the problem? The PSPACEcomplete 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 NPcomplete, and many games turn out to be PSPACEcomplete.
The game of checkers (draughts) is PSPACEcomplete 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 (EXPTIMEcomplete) because a game between two perfect players can be very long.
Note that the definition of PSPACEcomplete 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 PSPACEcomplete. That is why all the games were modified by playing them on an n × n board instead.
Another PSPACEcomplete problem is the problem of deciding whether a given string is a member of the language defined by a given contextsensitive grammar.
Search Encyclopedia

Featured Article
