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. 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 (1994) showed the weak derandomization result that BPL is contained in SC . [3] SC is the class of problems solvable in polynomial time and polylogarithmic space on a deterministic Turing machine; in other words, this result shows that, given polylogarithmic space, a deterministic machine can simulate logarithmic space probabilistic algorithms.
BPL is contained in NC and in L/poly . Saks and Zhou showed that BPL is contained in DSPACE(log3/2 n), [4] and in 2021 Hoza improved this to show BPL is contained in DSPACE. [5]