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. 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":
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.
| 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 |