Editing RL (complexity)

'''Randomized Logarithmic-space''' ('''RL'''),<ref>{{CZoo|RL|R#rl}}</ref> sometimes called '''RLP''' (Randomized Logarithmic-space Polynomial-time),<ref>A. Borodin, S.A. Cook, P.W. Dymond, W.L. Ruzzo, and M. Tompa. Two applications of inductive counting for complementation problems. SIAM Journal on Computing, 18(3):559&ndash;578. 1989.</ref> is the [[complexity class]] of [[computational complexity theory]] problems solvable in [[logarithmic space]] and [[polynomial time]] with [[probabilistic Turing machine]]s with [[one-sided error]]. It is named in analogy with [[RP (complexity)|RP]], which is similar but has no logarithmic space restriction.

==Definition==
The probabilistic Turing machines in the definition of '''RL''' never accept incorrectly but are allowed to reject incorrectly less than 1/3 of the time; this is called ''one-sided error''. The constant 1/3 is arbitrary; any ''x'' with 0 < ''x'' < 1 would suffice. This error can be made 2<sup>−''p''(''x'')</sup> times smaller for any polynomial ''p''(''x'') without using more than polynomial time or logarithmic space by running the algorithm repeatedly.

==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'''.

== References ==
{{reflist}}

{{ComplexityClasses}}

{{DEFAULTSORT:Rl (Complexity)}}
[[Category:Probabilistic complexity classes]]