BPL (complexity)
≈ 2 min read
Names in other languages
No names in other languages are held for this entry yet.
Article bodies are English and are not machine-translated. A name in another language is not a translation of the article.
In computational complexity theory, BPL (Bounded-error Probabilistic Logarithmic-space), sometimes called BPLP (Bounded-error Probabilistic Logarithmic-space Polynomial-time), 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.
In computational complexity theory, BPL (Bounded-error Probabilistic Logarithmic-space), sometimes called BPLP (Bounded-error Probabilistic Logarithmic-space Polynomial-time), 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. ==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 −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 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. 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 (\log^{3/2}(n)/\sqrt{\log \log n}) . In October 2026, OpenAI released a manuscript produced by an internal model, claiming that L = RL = BPL.
Text derived from https://en.wikipedia.org/w/index.php?oldid=1378940240 under CC BY-SA 4.0; modifications have been made.