NSPACE

This article does not cite any references or sources. Please help improve this article by adding citations to reliable sources. Unsourced material may be challenged and removed. (December 2009)

In computational complexity theory, 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 f(n) is the maximum number of tape cells that M scans on any input of length n.^[1] It is the non-deterministic counterpart of DSPACE.

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 =
• EXPSPACE = NEXPSPACE =

The last two results above follow from Savitch's theorem, which states that for any function f(n) ≥ log(n),

NSPACE(f(n)) ⊆ DSPACE(f²(n)).

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

NSPACE can be related to DTIME as follows. For any space constructible function s(n),

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

References

External Links

Complexity Zoo: NSPACE(f(n)).