RLP
Encyclopedia
In computational complexity theory
, RL (Randomized Logarithmic-space), sometimes called RLP (Randomized Logarithmic-space Polynomial-time), is the complexity class
of problems solvable in logarithmic space and polynomial time with probabilistic Turing machine
s with one-sided error. It is named in analogy with RP
, which is similar but has no logarithmic space restriction.
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.
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.
Nisan 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. 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.
Computational complexity theory
Computational complexity theory is a branch of the theory of computation in theoretical computer science and mathematics that focuses on classifying computational problems according to their inherent difficulty, and relating those classes to each other...
, RL (Randomized Logarithmic-space), sometimes called RLP (Randomized Logarithmic-space Polynomial-time), is the complexity class
Complexity class
In computational complexity theory, a complexity class is a set of problems of related resource-based complexity. A typical complexity class has a definition of the form:...
of problems solvable in logarithmic space and polynomial time with probabilistic Turing machine
Probabilistic Turing machine
In computability theory, a probabilistic Turing machine is a non-deterministic Turing machine which randomly chooses between the available transitions at each point according to some probability distribution....
s with one-sided error. It is named in analogy with RP
RP (complexity)
In complexity theory, RP is the complexity class of problems for which a probabilistic Turing machine exists with these properties:* It always runs in polynomial time in the input size...
, which is similar but has no logarithmic space restriction.
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.
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
NL (complexity)
In computational complexity theory, NL is the complexity class containing decision problems which can be solved by a nondeterministic Turing machine using a logarithmic amount of memory space....
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
BPL (complexity)
In computational complexity theory, BPL , sometimes called BPLP , is the complexity class of problems solvable in logarithmic space and polynomial time with probabilistic Turing machines with two-sided error...
, which is similar but allows two-sided error (incorrect accepts). RL contains L
L (complexity)
In computational complexity theory, L is the complexity class containing decision problems which can be solved by a deterministic Turing machine using a logarithmic amount of memory space...
, the problems solvable by deterministic Turing machines in log space, since its definition is just more general.
Nisan showed in 1992 the weak derandomization result that RL is contained in SC
SC (complexity)
In computational complexity theory, SC is the complexity class of problems solvable by a deterministic Turing machine in polynomial time and polylogarithmic space...
, 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. 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
SL (complexity)
In computational complexity theory, SL is the complexity class of problems log-space reducible to USTCON , which is the problem of determining whether there exists a path between two vertices in an undirected graph, otherwise described as the problem of determining whether two vertices are in the...
is equal to L.