Class Description

R_HL: Randomized Halting Logarithmic-Space

Has the same relation to L as RP does to P. The randomized machine must halt for every input and every setting of the random tape.

Contains undirected reachability (is there a path from vertex u to vertex v in an undirected graph?) [AKL+79].

Contained in RL.

Linked From

RL: Randomized Logarithmic-Space

Has the same relation to L as RP does to P. The randomized machine must halt with probability 1 on any input. It must also run in polynomial time (since otherwise we would just getNL).

Contains R_HL.

Contained in SC [Nis92].

[RTV05] give strong evidence that RL = L.

More about...