RL (complexity)

In computational complexity theory, RL, sometimes called RLP, is the complexity class of problems solvable in logarithmic space and polynomial time with probabilistic Turing machines.

the complexity class of problems solvable in logarithmic space and polynomial time with probabilistic Turing machines that 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/2 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.

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 BPLP, 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 derandomized. 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.