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.