Class Description

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)).

Linked From

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)).

More about...