Home > PSPACE
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.PSPACE is a strict superset of the set of context-sensitive languages. The following facts are known, where ⊂ means "proper subset", and ⊆ means "subset":
- NC ⊆ P ⊆ NP ⊆ PSPACE
- NC ⊂ PSPACE ⊂ EXPSPACE
- PSPACE-Complete ⊆ PSPACE
There are three ⊆ symbols on the first line. It is known that at least one of them must be a ⊂, but it is not known which. It is widely suspected that all three are ⊂. A solution of the P vs. NP question (the second ⊆) is worth $1,000,000. It is also widely suspected that the ⊆ on the last line should be a ⊂.
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.
An alternative characterization of PSPACE is the set of problems decidable by an alternating Turing machine in polynomial time.
A logical characterization of PSPACE is that it is the set of problems expressible in second order logic with the addition of a transitive closureIn mathematics, the transitive closure of a binary relation R on a set X is the smallest transitive relation on X that contains R''. For any relation R the transitive closure of R always exits. To see this note that the intersection of any family of trans 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 PHIn computational complexity theory, the complexity class PH is the union of all complexity classes in the polynomial hierarchy: : PH is contained in the complexity classes PPP (the class of problems that are decidable by a polynomial time Turing machine w.
Complexity classes
