NSPACE

In

.

Complexity classes

The measure NSPACE is used to define the

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 = ${\displaystyle \bigcup _{k\in \mathbb {N} }{\mathsf {NSPACE}}(n^{k})}$
• EXPSPACE = NEXPSPACE = ${\displaystyle \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) ≥ log n.

A further generalization is ASPACE, defined with

.

Relation with other complexity classes

DSPACE

NSPACE is the non-deterministic counterpart of

, we have that:

${\displaystyle {\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

, which are not useful when trying to represent actual computers. For this reason, NSPACE is limited in its usefulness to real-world applications.

References

External links

• Complexity Zoo: NSPACE(f(n))
  .