Class Description

PrSPACE(f(n)): Unbounded-Error Probabilistic f(n)-Space

Has the same relation to DSPACE(f(n)) as PP does to P. The Turing machine has to halt with probability 1 on every input.

Contained in DSPACE(f(n)²) [BCP83].

Equals Pr_HSPACE(f(n)) [Jun85].

Linked From

Pr_HSPACE(f(n)): Unbounded-Error Halting Probabilistic f(n)-Space

Has the same relation to DSPACE(f(n)) as PP does to P. The Turing machine has to halt on every input and every setting of the random tape.

Equals PrSPACE(f(n)) [Jun85].

More about...