|
In computational complexity theory, RLP is the complexity class of problems solvable in logarithmithic 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 both RP, which is the same but has no space restriction, and RL, which is the same but has no time restriction. It is contained in BPLP, which is similar but allows two-sided error (incorrect accepts). RLP also contains L, the problems solvable by deterministic Turing machines in log space, since its definition is just less restricted, and is contained in NL, the problems solvable by nondeterministic Turing machines in log space, because NL=RL. 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 determinining if a path exists between two vertices in an undirected graph; see SL for more information.
|
