|
In complexity theory the class
PSPACE is the set of decision problems that can be
solved by a Turing machine using a polynomial amount of memory, and unlimited time.
The definition is not affected by whether the Turing machine is deterministic or non-deterministic (this is a corollary of
Savitch's theorem). So
- PSPACE = NPSPACE.
The set 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.
|