# RL (complexity)

**Randomized Logarithmic-space** (**RL**),^{[1]} sometimes called **RLP** (Randomized Logarithmic-space Polynomial-time),^{[2]} is the complexity class of computational complexity theory problems solvable in logarithmic space and polynomial time with probabilistic Turing machines with one-sided error. It is named in analogy with RP, which is similar but has no logarithmic space restriction.

## Definition[edit]

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^{−p(x)} 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[edit]

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**,^{[3]} 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.^{[4]} 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[edit]

**^***Complexity Zoo*: RL**^**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–578. 1989.**^**Nisan, Noam (1992), "RL ⊆ SC",*Proceedings of the 24th ACM Symposium on Theory of computing (STOC '92)*, Victoria, British Columbia, Canada, pp. 619–623, doi:10.1145/129712.129772.**^**O. Reingold and L. Trevisan and S. Vadhan. Pseudorandom walks in biregular graphs and the RL vs. L problem, ECCC TR05-022, 2004.