Knowledge Base Wiki

In computational complexity theory, non-deterministic space or NSPACE is the computational resource describing the 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 problems that can be solved by a non-deterministic Turing machine, M, using space O(f(n)), where n is the length of the input.^[1]

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

REG = DSPACE(O(1)) = NSPACE(O(1)), where REG is the class of regular languages (nondeterminism does not add power in constant space).
NL = NSPACE(O(log n))
CSL = NSPACE(O(n)), where CSL is the class of context-sensitive languages.
PSPACE = NPSPACE = $\bigcup _{k\in \mathbb {N} }{\mathsf {NSPACE}}(n^{k})$
EXPSPACE = NEXPSPACE = $\bigcup _{k\in \mathbb {N} }{\mathsf {NSPACE}}(2^{n^{k}})$

The Immerman–Szelepcsényi theorem states that NSPACE(s(n)) is closed under complement for every function $s (n) \geq log n .$

A further generalization is ASPACE, defined with alternating Turing machines.

Relation with other complexity classes

DSPACE

NSPACE is the non-deterministic counterpart of DSPACE, the class of memory space on a deterministic Turing machine. First by definition, then by Savitch's theorem, we have that:

${\mathsf {DSPACE}}[s(n)]\subseteq {\mathsf {NSPACE}}[s(n)]\subseteq {\mathsf {DSPACE}}[(s(n))^{2}].$

Time

NSPACE can also be used to determine the time complexity of a deterministic Turing machine by the following theorem:

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^S(n)) by a deterministic one.^[2]

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 machines, which can represent actual computers. On the other hand, NSPACE describes the space complexity of non-deterministic Turing machines, which are not useful when trying to represent actual computers. For this reason, NSPACE is limited in its usefulness to real-world applications.

References

^ Sipser, Michael (2006). Introduction to the Theory of Computation (2nd ed.). Course Technology. pp. 303–304. ISBN 978-0-534-95097-2.
^ Goddard, Wayne (2008). Introducing the Theory of Computation. Jones and Bartlett Publishers, Inc. p. 183. ISBN 978-0-7637-4125-9.

External links

Complexity Zoo: NSPACE(f(n)).

[1] Sipser, Michael (2006). Introduction to the Theory of Computation (2nd ed.). Course Technology. pp. 303–304. ISBN 978-0-534-95097-2.

[2] Goddard, Wayne (2008). Introducing the Theory of Computation. Jones and Bartlett Publishers, Inc. p. 183. ISBN 978-0-7637-4125-9.

[1]

[2]

Complexity classes
Considered feasible	DLOGTIME AC⁰ ACC⁰ TC⁰ L SL RL FL NL NL-complete NC SC CC P P-complete ZPP RP BPP BQP APX FP
Suspected infeasible	UP NP NP-complete NP-hard co-NP co-NP-complete TFNP FNP AM QMA PH ⊕P PP #P #P-complete IP PSPACE PSPACE-complete
Considered infeasible	EXPTIME NEXPTIME EXPSPACE 2-EXPTIME ELEMENTARY PR R RE ALL
Class hierarchies	Polynomial hierarchy Exponential hierarchy Grzegorczyk hierarchy Arithmetical hierarchy Boolean hierarchy
Families of classes	DTIME NTIME DSPACE NSPACE Probabilistically checkable proof Interactive proof system
List of complexity classes