NSPACE
|
|
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:
- <math>\mbox{NPSPACE} = \bigcup_{k\in\mathbb{N}} \mbox{NSPACE}(n^k)<math>Template:Comp-sci-stub