Editing NSPACE (section)

==Complexity classes==

The measure NSPACE is used to define the [[complexity class]] whose solutions can be determined by a [[non-deterministic Turing machine]]. The [[complexity class]] NSPACE(''f''(''n'')) is the set of [[decision problem]]s that can be solved by a [[non-deterministic Turing machine]], ''M'', using space ''O''(''f''(''n'')), where ''n'' is the length of the input.<ref>{{cite book|last=Sipser|first=Michael|title=Introduction to the Theory of Computation (2nd ed.)|url=https://archive.org/details/introductiontoth00mich|url-access=limited|year=2006|publisher=Course Technology|isbn=978-0-534-95097-2|pages=[https://archive.org/details/introductiontoth00mich/page/n323 303]–304}}</ref>

Several important complexity classes can be defined in terms of ''NSPACE''. These include:

* [[regular language|REG]] = DSPACE(''O''(1)) = NSPACE(''O''(1)), where REG is the class of [[regular language]]s (nondeterminism does not add power in constant space).
* [[NL (complexity)|NL]] = NSPACE(''O''(log&nbsp;''n''))
* [[context-sensitive language|CSL]] = NSPACE(''O''(''n'')), where CSL is the class of [[context-sensitive language]]s.
* [[PSPACE]] = NPSPACE = <math>\bigcup_{k\in\mathbb{N}} \mathsf{NSPACE}(n^k)</math>
* [[EXPSPACE]] = NEXPSPACE = <math>\bigcup_{k\in\mathbb{N}} \mathsf{NSPACE}(2^{n^k})</math>

The [[Immerman–Szelepcsényi theorem]] states that NSPACE(''s''(''n'')) is closed under complement for every function {{math|''s''(''n'') ≥ log ''n''.}}

A further generalization is ASPACE, defined with [[alternation (complexity)|alternating Turing machines]].