In complexity theory, a decision problem is PSPACEcomplete if it is in the complexity class PSPACE, and every problem in PSPACE can be reduced to it in polynomial time (see complete (complexity)). The problems that are PSPACEcomplete can be thought of as the hardest problems in PSPACE, because a solution to any one such problem could easily be used to solve any other problem in PSPACE. These problems are widely suspected to be outside of the more famous complexity classes P and NP, but that is not known. It is known that they lie outside of the small class NC.
Contents
Discussion
The first known PSPACEcomplete problem was the word problem for deterministic contextsensitive grammars. In the word problem for contextsensitive grammars, one is given a set of grammatical transformations which can increase, but cannot decrease, the length of a sentence, and wishes to determine if a given sentence could be produced by these transformations. The technical condition of "determinism" (implying roughly that each transformation makes it obvious that it was used) ensures that this process can be solved in polynomial space, and S.Y. Kuroda's 1964 work "Classes of languages and linearbounded automata"^{[1]} showed that any (possibly nondeterministic) program computable in linear space could be converted into the parsing of a contextsensitive grammar, in a way which preserves determinism.
In 1970, Savitch's theorem showed that PSPACE is closed under nondeterminism, implying that even nondeterministic contextsensitive grammars are in PSPACE.
But the archetypal PSPACEcomplete problem is generally taken to be the quantified Boolean formula problem (usually abbreviated to QBF or TQBF; the T stands for "true"), a generalization of the first known NPcomplete problem, the Boolean satisfiability problem (SAT). The satisfiability problem 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:
Full article ▸
