Sometimes the name
RL is reserved for the class of problems solvable by logarithmic-space probabilistic machines in
unbounded time. However, this class can be shown to be equal to
NL using a probabilistic counter, and so is usually referred to as
NL instead; this also shows that
RL is contained in
NL.
RL is contained in
BPL, which is similar but allows two-sided error (incorrect accepts).
RL contains
L, the problems solvable by
deterministic Turing machines in log space, since its definition is just more general.
Noam Nisan showed in 1992 the weak
derandomization result that
RL is contained in
SC, the class of problems solvable in polynomial time and polylogarithmic space on a deterministic Turing machine; in other words, given
polylogarithmic space, a deterministic machine can simulate
logarithmic space probabilistic algorithms. It is believed that
RL is equal to
L, that is, that polynomial-time logspace computation can be completely derandomized; major evidence for this was presented by Reingold et al. in 2005. A proof of this is the holy grail of the efforts in the field of unconditional derandomization of complexity classes. A major step forward was Omer Reingold's proof that
SL is equal to
L. == References ==