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 9 September 2013.
HTML page formatted Mon Feb 2 13:10:39 2015.
Cite this as:
Paul E. Black, "BPP", in Dictionary of Algorithms and Data Structures [online], Vreda Pieterse and Paul E. Black, eds. 9 September 2013. (accessed TODAY) Available from: http://www.nist.gov/dads/HTML/bpp.html