Definition: The class of languages for which a membership computation by a probabilistic Turing machine halts in polynomial time with the right answer (accept or reject) at least 2/3 of the time. "BPP" means "Bounded error Probability in Polynomial" time.
Also known as bounded error probability in polynomial time.
See also ZPP, RP, NP, complexity class.
Note: By repeating the run, the chance of error may be arbitrarily reduced.
After [Hirv01, page 19].
Scott Aaronson's Complexity Zoo
If you have suggestions, corrections, or comments, please get in touch with Paul Black.
Entry modified 5 January 2021.
HTML page formatted Tue Jan 5 09:25:05 2021.
Cite this as:
Paul E. Black, "BPP", in Dictionary of Algorithms and Data Structures [online], Paul E. Black, ed. 5 January 2021. (accessed TODAY) Available from: https://www.nist.gov/dads/HTML/bpp.html