- NESPACE
In
computational complexity theory , thecomplexity class NESPACE is the set ofdecision problem s that can be solved by anon-deterministic Turing machine in space O(2n). IfESPACE is defined as the set of decision problems that can be solved by adeterministic Turing machine in space O(2n), then ESPACE is a subset of NESPACE. However, if it is instead defined as the set of decision problems that can be solved by adeterministic Turing machine in space 2O(n), then NESPACE is a proper subset of ESPACE, bySavitch's theorem and thespace hierarchy theorem .In any case, the closure of either class under
polynomial-time many-one reduction s isEXPSPACE .
Wikimedia Foundation. 2010.