NSPACE

From Wikipedia, the free encyclopedia

You have new messages (last change).

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.

The complexity class NPSPACE can be defined in terms of NSPACE as follows:

\mbox{NPSPACE} = \bigcup_{k\in\mathbb{N}} \mbox{NSPACE}(n^k)
Comp Sci logo This computer science-related article is a stub. You can help Wikipedia by expanding it.
Retrieved from "http://en.wikipedia.org../../../n/s/p/NSPACE_564e.html"
In other languages