Class Description

BP_HSPACE(f(n)): Bounded-Error Halting 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 on every input and every random tape setting.

Contains R_HSPACE(f(n)).

Is contained in DSPACE(f(n)^3/2) [SZ95].

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 BP_HSPACE(f(n)).

More about...

R_HSPACE(f(n)): One-Sided Error Halting Probabilistic f(n)-Space

Has the same relation to BP_HSPACE(f(n)) as RP does to BPP.

More about...