RLP

(Redirected from 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.