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.
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.
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 (1994) showed the weak derandomization result that BPL is contained in SC.