RL (complexity)

Randomized Logarithmic-space (RL),[1] sometimes called RLP (Randomized Logarithmic-space Polynomial-time),[2] is the complexity class of computational complexity theory problems solvable in logarithmic space and polynomial time with probabilistic Turing machines with one-sided error. It is named in analogy with RP, which is similar but has no logarithmic space restriction.

  1. ^ Complexity Zoo: RL
  2. ^ A. Borodin, S.A. Cook, P.W. Dymond, W.L. Ruzzo, and M. Tompa. Two applications of inductive counting for complementation problems. SIAM Journal on Computing, 18(3):559–578. 1989.