Discover

In complexity theory the class 'PSPACE', which equals 'NPSPACE' by Savitch's theorem, is the set of decision problems that can be solved by a deterministic or nondeterministic Turing machine using a polynomial amount of memory and unlimited time (either of these machine types determines the same class).
'PSPACE' is a strict superset of the set of context-sensitive languages. The following relationships are known between the classes 'NL', 'P', 'NP', 'PSPACE', 'EXPTIME' and 'EXPSPACE':
:$mbox\{NL\}\; subseteq\; mbox\{P\}\; subseteq\; mbox\{NP\}\; subseteq\; mbox\{PSPACE\}$
:$mbox\{PSPACE\}\; subseteq\; mbox\{EXPTIME\}\; subseteq\; mbox\{EXPSPACE\}$
:$mbox\{NL\}\; subsetneq\; mbox\{PSPACE\}\; subsetneq\; mbox\{EXPSPACE\}$
There are three $subseteq$ (subset or equal) symbols on the first line and two on the second line. It is known that at in each line, least one of them must be a $subsetneq$ symbol, but it is not known which. It is widely suspected that all are $subsetneq$.
In contrast, the containments in the third line are all known to be strict. The first follows from direct diagonalization (the space hierarchy theorem, $mbox\{NL\}\; subsetneq\; mbox\{NPSPACE\}$) and the fact that $mbox\{PSPACE\}\; =\; mbox\{NPSPACE\}$ via Savitch's theorem. The second follows simply from the space hierarchy theorem.
The hardest problems in 'PSPACE' are the 'PSPACE-Complete' problems. See 'PSPACE-Complete' for examples of problems that are suspected to be in 'PSPACE' but not in 'NP'.

Contents

Other characterizations

References

Other characterizations

An alternative characterization of 'PSPACE' is the set of problems decidable by an alternating Turing machine in polynomial time, sometimes called 'APTIME' or just 'AP'.
A logical characterization of 'PSPACE' is that it is the set of problems expressible in second-order logic with the addition of a transitive closure operator. A full transitive closure is not needed; a commutative transitive closure and even weaker forms suffice. It is the addition of this operator that (possibly) distinguishes 'PSPACE' from 'PH'.
A major result of complexity theory is that 'PSPACE' can be characterized as all the languages recognizable by a particular interactive proof system, the one defining the class 'IP'. In this system, there is an all-powerful prover trying to convince a randomized polynomial-time verifier that a string is in the language. It should be able to convince the verifier with high probability if the string is in the language, but should not be able to convince it except with low probability if the string is not in the language.

References

★ The Complexity Zoo: PSPACE

★ Introduction to the Theory of Computation, Michael Sipser, , , PWS Publishing, 1997, ISBN 0-534-94728-X Section 8.2–8.3 (The Class PSPACE, PSPACE-completeness), pp.281–294.

★ Computational Complexity, Christos Papadimitriou, , , Addison Wesley, 1993, ISBN 0-201-53082-1 Chapter 19: Polynomial space, pp. 455–490.