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.

Sometimes the name RL is reserved for the class of problems solvable by logarithmic-space probabilistic machines in unbounded time.

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.

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.