The PSPACE reference article from the English Wikipedia on 24-Jul-2004 (provided by Fixed Reference: snapshots of Wikipedia from wikipedia.org)

PSPACE

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.

Important complexity classes

P | NP | Co-NP | NP-C | Co-NP-C | NP-hard | UP | #P | #P-C | NC | P-C

PSPACE | PSPACE-C | EXPTIME | EXPSPACE | BQP | BPP | RP | ZPP | PCP | IP | PH

This is the "PSPACE" reference article from the English Wikipedia. All text is available under the terms of the GNU Free Documentation License. See also our Disclaimer.