Editing NSPACE

In [[computational complexity theory]], non-deterministic space or '''NSPACE''' is the [[computational resource]] describing the [[Memory space (computational resource)|memory space]] for a [[non-deterministic Turing machine]].  It is the non-deterministic counterpart of [[DSPACE]].

==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]].

==Relation with other complexity classes==

===DSPACE===

NSPACE is the non-deterministic counterpart of [[DSPACE]], the class of [[Memory space (computational resource)|memory space]] on a [[deterministic Turing machine]].  First by definition, then by [[Savitch's theorem]], we have that:
<blockquote>
<math>\mathsf{DSPACE}[s(n)] \subseteq \mathsf{NSPACE}[s(n)] \subseteq \mathsf{DSPACE}[(s(n))^2].</math>
</blockquote>

===Time===

NSPACE can also be used to determine the time complexity of a [[deterministic Turing machine]] by the following theorem:
<blockquote>
If a language ''L'' is decided in space ''S''(''n'') (where ''S''(''n'') ≥ log ''n'') by a non-deterministic TM, then there exists a constant ''C'' such that ''L'' is decided in time ''O''(''C''<sup>''S''(''n'')</sup>) by a deterministic one.<ref>{{cite book|last=Goddard|first=Wayne|title=Introducing the Theory of Computation|year=2008|publisher=Jones and Bartlett Publishers, Inc.|isbn=978-0-7637-4125-9|pages=183}}</ref>
</blockquote>

==Limitations==

The measure of [[space complexity]] in terms of [[DSPACE]] is useful because it represents the total amount of memory that an actual computer would need to solve a given [[computational problem]] with a given [[algorithm]]. The reason is that DSPACE describes the space complexity used by [[deterministic Turing machine]]s, which can represent actual computers. On the other hand, NSPACE describes the space complexity of [[non-deterministic Turing machine]]s, which are not useful when trying to represent actual computers. For this reason, NSPACE is limited in its usefulness to real-world applications.

==References==
{{Reflist}}

==External links==
*{{ComplexityZoo|NSPACE(''f''(''n''))|N#nspace}}.

{{ComplexityClasses}}

{{DEFAULTSORT:Nspace}}
[[Category:Complexity classes]]
[[Category:Computational resources]]