Nondeterministic space

In computational complexity theory, non-deterministic space or NSPACE is the computational resource describing the memory space for a non-deterministic Turing machine. It is the non-deterministic counterpart of DSPACE.

The measure NSPACE is used to define the complexity class whose solutions can be determined by a non-deterministic Turing machine. The complexity class NSPACE(f(n)) is the set of decision problems that can be solved by a non-deterministic Turing machine, M, using space O(f(n)), where n is the length of the input.

Several important complexity classes can be defined in terms of NSPACE. These include:

The Immerman–Szelepcsényi theorem states that NSPACE(s(n)) is closed under complement for every function s(n) ≥ log n.

A further generalization is ASPACE, defined with alternating Turing machines.

NSPACE is the non-deterministic counterpart of DSPACE, the class of memory space on a deterministic Turing machine. First by definition, then by Savitch's theorem, we have that:

${\displaystyle {\mathsf {DSPACE}}[s(n)]\subseteq {\mathsf {NSPACE}}[s(n)]\subseteq {\mathsf {DSPACE}}[(s(n))^{2}].}$

...
Wikipedia