Class Description

BPSPACE(f(n)): Bounded-Error Probabilistic f(n)-Space

The class of decision problems solvable in O(f(n))-space with error probability at most 1/3, by a Turing machine that halts with probability 1 on every input.

Contains RSPACE(f(n)) and BPHSPACE(f(n)).

Linked From

DTISP(t(n),s(n)): Simultaneous t(n)-Time and s(n)-Space

The class of decision problems solvable by a Turing machine that uses time O(t(n)) and space O(s(n)) simultaneously.

Thus SC = DTISP(poly,polylog) for example.

Defined in [Nis92], where it was also shown that for all space-constructible s(n)=Ω(log n), BPSPACE(s(n)) is contained in DTISP(2O(s(n)),s2(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...