BPP

Summary

BPP, for bounded-error probabilistic polynomial time, is a complexity class of decision problems. A problem is in BPP when a polynomial-time probabilistic Turing machine solves it with error probability at most $1/3$ on every input. It is the usual formal notion of a problem that is efficiently solvable with randomness. It contains P, RP and ZPP, and it lies in the second level of the polynomial hierarchy. Many researchers conjecture that $\mathrm{BPP} = \mathrm{P}$.