- BPL (complexity)
In

computational complexity theory ,**BPL**(Bounded-error Probabilistic Logarithmic-space), [*[*] sometimes called*http://qwiki.stanford.edu/wiki/Complexity_Zoo:B#bpl Complexity Zoo: BPL*]**BPLP**(Bounded-error Probabilistic Logarithmic-space Polynomial-time), [*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.*] is thecomplexity class of problems solvable inlogarithmic space andpolynomial time withprobabilistic Turing machine s withtwo-sided error . It is named in analogy with**BPP**, which is similar but has no logarithmic space restriction.The probabilistic Turing machines in the definition of

**BPL**may only accept or reject incorrectly less than 1/3 of the time; this is called "two-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.Since two-sided error is more general than one-sided error,

**RL**and its complement**co-RL**are contained in**BPL**.**BPL**is also contained in**PL**, which is similar except that the error bound is 1/2, instead of a constant less than 1/2; like the class**PP**, the class**PL**is less practical because it may require a large number of rounds to reduce the error probability to a small constant.Nisan showed in 1992 the weak

derandomization result thatis contained inBPL **SC**[*N. Nisan. RL is contained in SC, Proceedings of ACM STOC'92, pp. 619-623, 1992.*] , the class of problems solvable in polynomial time and polylogarithmic space on a deterministic Turing machine; in other words, given "polylogarithmic" space, a deterministic machine can simulate "logarithmic" space probabilistic algorithms.**References**

*Wikimedia Foundation.
2010.*