Editing PSPACE (section)

== Relation among other classes ==
[[Image:Complexity subsets pspace.svg|300px|thumb|right|A representation of the relation among complexity classes]]
The following relations are known between PSPACE and the complexity classes [[NL (complexity)|NL]], [[P (complexity)|P]], [[NP (complexity)|NP]], [[PH (complexity)|PH]], [[EXPTIME]] and [[EXPSPACE]] (we use here <math>\subset</math> to denote strict containment, meaning a proper subset, whereas <math>\subseteq</math> includes the possibility that the two sets are the same):

:<math>\begin{array}{l}
\mathsf{NL \subseteq P \subseteq NP \subseteq PH \subseteq PSPACE}\\
\mathsf{PSPACE \subseteq EXPTIME \subseteq EXPSPACE}\\
\mathsf{NL \subset PSPACE \subset EXPSPACE}\\
\mathsf{P\subset EXPTIME}\end{array}</math>

From the third line, it follows that both in the first and in the second line, at least one of the set containments must be strict, but it is not known which.  It is widely suspected that all are strict.

The containments in the third line are both known to be strict.  The first follows from direct diagonalization (the [[space hierarchy theorem]], NL ⊂ NPSPACE) and the fact that PSPACE {{=}} 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.