BPL (complexity)

In computational complexity theory, BPL (Bounded-error Probabilistic Logarithmic-space),[1] sometimes called BPLP (Bounded-error Probabilistic Logarithmic-space Polynomial-time),[2] is the complexity class of problems solvable in logarithmic space and polynomial time with probabilistic Turing machines with two-sided error. It is named in analogy with BPP, which is similar but has no logarithmic space restriction.

  1. ^ "Complexity Zoo: BPL". Archived from the original on 2012-08-05. Retrieved 2011-10-04.
  2. ^ Borodin, A.; Cook, S. A.; Dymond, P. W.; Ruzzo, W. L.; Tompa, M. (1989), "Two applications of inductive counting for complementation problems", SIAM Journal on Computing, 18 (3): 559–578, CiteSeerX 10.1.1.394.1662, doi:10.1137/0218038