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.
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 RHL.
[RTV05] give strong evidence that RL = L.