linguistic:paraphrasing, information:classification
Relationships between classes

The space hierarchy theorem states that, for all space-constructible functions f (n), {\displaystyle f(n),} there exists a problem that can be solved by a machine with f (n) {\displaystyle f(n)} memory space, but cannot be solved by a machine with asymptotically less than f (n) {\displaystyle f(n)} space.

The following containments between complexity classes hold. D T I M E (f (n)) ⊆ D S P A C E (f (n)) ⊆ N S P A C E (f (n)) ⊆ D T I M E (2 O (f (n))) {\displaystyle {\mathsf {DTIME}}(f(n))\subseteq {\mathsf {DSPACE}}(f(n))\subseteq {\mathsf {NSPACE}}(f(n))\subseteq {\mathsf {DTIME}}\left(2^{O(f(n))}\right)}

Furthermore, Savitch's theorem gives the reverse containment that if f ∈ Ω (log (n)), {\displaystyle f\in \Omega (\log(n)),} N S P A C E (f (n)) ⊆ D S P A C E ((f (n)) 2). {\displaystyle {\mathsf {NSPACE}}(f(n))\subseteq {\mathsf {DSPACE}}\left((f(n))^{2}\right).}

As a direct corollary, P S P A C E = N P S P A C E. {\displaystyle {\mathsf {PSPACE}}={\mathsf {NPSPACE}}.} This result is surprising because it suggests that non-determinism can reduce the space necessary to solve a problem only by a small amount. In contrast, the exponential time hypothesis conjectures that for time complexity, there can be an exponential gap between deterministic and non-deterministic complexity.

The Immerman–Szelepcsényi theorem states that, again for f ∈ Ω (log (n)), {\displaystyle f\in \Omega (\log(n)),} N S P A C E (f (n)) {\displaystyle {\mathsf {NSPACE}}(f(n))} is closed under complementation. This shows another qualitative difference between time and space complexity classes, as nondeterministic time complexity classes are not believed to be closed under complementation; for instance, it is conjectured that NP ≠ co-NP.