Class Description

NSPACE(f(n)): Nondeterministic f(n)-Space

Same as NPSPACE, but with f(n)-space (for some constructible function f) rather than polynomial-space machines.

Contained in DSPACE(f(n)2) [Sav70], and indeed RevSPACE(f(n)2) 95|[CP95].

NSPACE(nk) is strictly contained in NSPACE(nk+ε) for ε>0 [Iba72] (actually the hierarchy theorem is stronger than this, but pretty technical to state).

Linked From

CSL: Context Sensitive Languages

The class of languages generated by context-sensitive grammars.

Equals NSPACE(n) [Kur64].

More about...


DSPACE(f(n)): Deterministic f(n)-Space

The class of decision problems solvable by a Turing machine in space O(f(n)).

The Space Hierarchy Theorem: For constructible f(n) greater than logn, DSPACE(f(n)) is strictly contained in DSPACE(f(n) log(f(n))) [HLS65].

For space constructible f(n), strictly contains DTIME(f(n)) [HPV77].

DSPACE(n) does not equal NP (though we have no idea if one contains the other)!

See also: NSPACE(f(n)).

More about...


GAN-SPACE(f(n)): Games Against Nature f(n)-Space

The class of problems decidable by an O(f(n))-space Turing machine with two kinds of quantifiers: existential and randomized.

Contains NSPACE(f(n)) and BPSPACE(f(n)), and is contained in AUC-SPACE(f(n)).

By linear programming, GAN-SPACE(log n) is contained in P.

More about...


RSPACE(f(n)): Randomized f(n)-Space

Same as RL, but for O(f(n))-space instead of logarithmic-space. (Just as an RL machine must run in polynomial time, so an RSPACE(f(n)) machine must run in 2O(f(n)) time.)

Contained in NSPACE(f(n)) and BPSPACE(f(n)).

More about...