Editing Space complexity (section)

==Relationships between classes==

The [[space hierarchy theorem]] states that, for all [[space-constructible function]]s <math>f(n),</math> there exists a problem that can be solved by a machine with <math>f(n)</math> memory space, but cannot be solved by a machine with asymptotically less than <math>f(n)</math> space.

The following containments between complexity classes hold.<ref>{{citation |title=Computational Complexity : A Modern Approach |edition=draft|year=2007|first1=Sanjeev|last1=Arora|author1-link=Sanjeev Arora|first2=Boaz|last2=Barak|isbn=9780511804090 |page=76 |url=https://theory.cs.princeton.edu/complexity/book.pdf}}</ref>
<math display=block>\mathsf{DTIME}(f(n)) \subseteq \mathsf{DSPACE}(f(n)) \subseteq \mathsf{NSPACE}(f(n)) \subseteq \mathsf{DTIME}\left(2^{O(f(n))}\right)</math>

Furthermore, [[Savitch's theorem]] gives the reverse containment that if <math>f \in \Omega(\log(n)),</math>
<math display=block>\mathsf{NSPACE}(f(n)) \subseteq \mathsf{DSPACE}\left((f(n))^2\right).</math>

As a direct corollary, <math>\mathsf{PSPACE} = \mathsf{NPSPACE}.</math> 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 <math>f\in\Omega(\log(n)),</math> <math>\mathsf{NSPACE}(f(n))</math> 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]].<ref>{{citation
 | last = Immerman | first = Neil | authorlink = Neil Immerman
 | doi = 10.1137/0217058
 | issue = 5
 | journal = SIAM Journal on Computing
 | mr = 961049
 | pages = 935–938
 | title = Nondeterministic space is closed under complementation
 | url = http://www.cs.umass.edu/~immerman/pub/space.pdf
 | volume = 17
 | year = 1988}}</ref><ref>{{citation
 | last = Szelepcsényi | first = Róbert | author-link = Róbert Szelepcsényi
 | journal = Bulletin of the EATCS
 | pages = 96–100
 | title = The method of forcing for nondeterministic automata
 | volume = 33
 | year = 1987}}</ref>