{{Short description|Concept in computational complexity theory}} In computational complexity theory, '''BPL''' (Bounded-error Probabilistic Logarithmic-space),<ref>{{Cite web |url=http://qwiki.stanford.edu/index.php/Complexity_Zoo:B |title=Complexity Zoo: BPL |access-date=2011-10-04 |archive-url=https://web.archive.org/web/20120805060809/http://qwiki.stanford.edu/index.php/Complexity_Zoo:B#bpl |archive-date=2012-08-05 |url-status=dead }}</ref> sometimes called '''BPLP''' (Bounded-error Probabilistic Logarithmic-space Polynomial-time),<ref>{{citation | last1 = Borodin | first1 = A. | author1-link = Allan Borodin | last2 = Cook | first2 = S. A. | author2-link = Stephen Cook | last3 = Dymond | first3 = P. W. | last4 = Ruzzo | first4 = W. L. | last5 = Tompa | first5 = M. | doi = 10.1137/0218038 | issue = 3 | journal = SIAM Journal on Computing | pages = 559–578 | title = Two applications of inductive counting for complementation problems | volume = 18 | year = 1989| citeseerx = 10.1.1.394.1662 }}</ref> 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'' < 1/2 would suffice. This error can be made 2<sup>−''p''(''x'')</sup> 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.
{{harvtxt|Nisan|1994}} showed the weak derandomization result that '''BPL''' is contained in '''SC'''.<ref>{{citation | last = Nisan | first = N. | authorlink = Noam Nisan | doi = 10.1007/BF01205052 | id = An earlier version of this paper appeared at the 1992 Symposium on Theory of Computing | issue = 1 | journal = Computational Complexity | pages = 1–11 | title = RL ⊆ SC | volume = 4 | year = 1994}}</ref> 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<sup>3/2</sup> n),<ref>[http://pages.cs.wisc.edu/~dieter/Courses/2007s-CS810/Scribes/PS/lecture11.ps Complexity theory lecture notes]</ref> and in 2021 Hoza improved this to show '''BPL''' is contained in '''DSPACE''' <math> (\log^{3/2}(n)/\sqrt{\log \log n}) </math>.<ref>{{cite web | url=https://eccc.weizmann.ac.il/report/2021/048/ | title=Better Pseudodistributions and Derandomization for Space-Bounded Computation | year=2021 | last1=Hoza | first1=William }}</ref>
== References == {{reflist}}
{{ComplexityClasses}}
Category:Probabilistic complexity classes