RL (complexity)

In computational complexity theory, RLP, often referred to as simply RL, is 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.

RLP is contained in RP, which is the same but has no space restriction, and in BPLP, which is similar but allows two-sided error (incorrect accepts). It is also contained in NL, since NL has a probabilistic reformulation similar to RLP but without the time restriction. RLP contains L, the problems solvable by deterministic Turing machines in log space, since its definition is just more general. The class SL is also contained in RLP, because there is a randomized log-space, polynomial-time algorithm for the SL-complete problem USTCON, the problem of determining if a path exists between two vertices in an undirected graph (as well as because SL=L); see SL for more information.