PSPACE-complete Guide, Meaning , Facts, Information and Description
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:
The game of checkers (draughts) is PSPACE-complete when generalized so that it can be played on an n × n board. So are the generalized versions of the games cex and Reversi and the solitaire games Rush Hour, mahjong, Atomix and Sokoban. Some other generalized games, such as chess 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.