Randomized Logarithmic-space (RL), sometimes called RLP (Randomized Logarithmic-space Polynomial-time), is the
complexity class
In computational complexity theory, a complexity class is a set (mathematics), set of computational problems of related resource-based computational complexity, complexity. The two most commonly analyzed resources are time complexity, time and spa ...
of
computational complexity theory
In theoretical computer science and mathematics, computational complexity theory focuses on classifying computational problems according to their resource usage, and relating these classes to each other. A computational problem is a task solved ...
problems solvable in
logarithmic space
In computational complexity theory, L (also known as LSPACE or DLOGSPACE) is the complexity class containing decision problems that can be solved by a deterministic Turing machine using a logarithmic amount of writable memory space., Definition& ...
and
polynomial time with
probabilistic Turing machine
In theoretical computer science, a probabilistic Turing machine is a non-deterministic Turing machine that chooses between the available transitions at each point according to some probability distribution. As a consequence, a probabilistic Turi ...
s with
one-sided error
In computing, a Monte Carlo algorithm is a randomized algorithm whose output may be incorrect with a certain (typically small) probability. Two examples of such algorithms are Karger–Stein algorithm and Monte Carlo algorithm for minimum Feedba ...
. It is named in analogy with
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
−''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
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
Noam Nisan ( he, נעם ניסן; born June 20, 1961) is an Israeli computer scientist, a professor of computer science at the Hebrew University of Jerusalem. He is known for his research in computational complexity theory and algorithmic game th ...
showed in 1992 the weak
derandomization result that RL is contained in
SC, 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.
[O. Reingold and L. Trevisan and S. Vadhan. Pseudorandom walks in biregular graphs and the RL vs. L problem, , 2004.] 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
{{DEFAULTSORT:Rl (Complexity)
Probabilistic complexity classes