Class Description

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

More about...


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

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

More about...