In
computational complexity theory
In theoretical computer science and mathematics, computational complexity theory focuses on classifying computational problems according to their resource usage, and relating these classes to each other. A computational problem is a task solved ...
, BPL (Bounded-error Probabilistic Logarithmic-space), sometimes called BPLP (Bounded-error Probabilistic Logarithmic-space Polynomial-time), is the
complexity class
In computational complexity theory, a complexity class is a set (mathematics), set of computational problems of related resource-based computational complexity, complexity. The two most commonly analyzed resources are time complexity, time and spa ...
of problems solvable in
logarithmic space
In computational complexity theory, L (also known as LSPACE or DLOGSPACE) is the complexity class containing decision problems that can be solved by a deterministic Turing machine using a logarithmic amount of writable memory space., Definition& ...
and
polynomial time with
probabilistic Turing machine
In theoretical computer science, a probabilistic Turing machine is a non-deterministic Turing machine that chooses between the available transitions at each point according to some probability distribution. As a consequence, a probabilistic Turi ...
s with
two-sided error
In computing, a Monte Carlo algorithm is a randomized algorithm whose output may be incorrect with a certain (typically small) probability. Two examples of such algorithms are Karger's algorithm, Karger–Stein algorithm and Monte Carlo algorithm ...
. It is named in analogy with
BPP
BPP may refer to:
Education
* BPP Holdings, a holding company based in the United Kingdom
* BPP Law School, a law school based in the United Kingdom and a constituent school of BPP University
* BPP University, a private university based in the ...
, which is similar but has no logarithmic space restriction.
Error model
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.
Related classes
Since two-sided error is more general than one-sided error,
RL and its
complement
A complement is something that completes something else.
Complement may refer specifically to:
The arts
* Complement (music), an interval that, when added to another, spans an octave
** Aggregate complementation, the separation of pitch-clas ...
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.
showed the weak
derandomization result that BPL is contained in
SC. 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 In computational complexity theory, L/poly is the complexity class of logarithmic space machines with a polynomial amount of advice. L/poly is a non-uniform logarithmic space class, analogous to the non-uniform polynomial time class P/poly.
Forma ...
. Saks and Zhou showed that BPL is contained in DSPACE(log
3/2 n), and in 2021 Hoza improved this to show BPL is contained in DSPACE
.
References
{{ComplexityClasses
Probabilistic complexity classes