Editing RL (complexity) (section)

==Relation to other complexity classes==
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 (complexity)|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 (complexity)|BPL]]''', which is similar but allows two-sided error (incorrect accepts). '''RL''' contains '''[[L (complexity)|L]]''', the problems solvable by [[deterministic Turing machine]]s 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 (complexity)|SC]]''',<ref>{{citation
 | last = Nisan | first = Noam | author-link = Noam Nisan
 | contribution = RL ⊆ SC
 | doi = 10.1145/129712.129772
 | location = Victoria, British Columbia, Canada
 | pages = 619–623
 | title = Proceedings of the 24th ACM Symposium on Theory of computing (STOC '92)
 | year = 1992}}.</ref> 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.<ref>O. Reingold and [[Luca Trevisan|L. Trevisan]] and S. Vadhan. Pseudorandom walks in biregular graphs and the RL vs. L problem, {{ECCC|2005|05|022}}, 2004.</ref> 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 (complexity)|SL]]''' is equal to '''L'''.