NESPACE

From Wikipedia, the free encyclopedia

In computational complexity theory, the complexity class NESPACE is the set of decision problems that can be solved by a non-deterministic Turing machine in space O(2ⁿ). If ESPACE is defined as the set of decision problems that can be solved by a deterministic Turing machine in space O(2ⁿ), then ESPACE is a subset of NESPACE. However, if it is instead defined as the set of decision problems that can be solved by a deterministic Turing machine in space 2^O(n), then NESPACE is a proper subset of ESPACE, by Savitch's theorem and the space hierarchy theorem.

In any case, the closure of either class under polynomial-time many-one reductions is EXPSPACE.