NSPACE

From Wikipedia, the free encyclopedia

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 using space O(f(n)), and unlimited time. 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))
  • PSPACE = NPSPACE = \bigcup_{k\in\mathbb{N}} \mbox{NSPACE}(n^k)
  • EXPSPACE = NEXPSPACE = \bigcup_{k\in\mathbb{N}} \mbox{NSPACE}(2^{n^k})

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)).
Comp Sci logo This computer science-related article is a stub. You can help Wikipedia by expanding it.