Bounded-error Probabilistic Polynomial Time (BPP)

A language $L$ is said to be solvable in Bounded-error Probabilistic Polynomial Time (BPP) if there is some machine $M$ that is:

• Probabilistically “Sound”: $\text{if }w\notin L\text{ then Prob}(M(w)=1)\le \frac{1}{3}$
• Probabilistically “Complete”: $\text{if }w\in L\text{ then Prob}(M(w)=1)\ge \frac{2}{3}$
• Polynomial-time: $T(n)\in O(n^k)\text{ for some }k>0$

This class corresponds to Monte Carlo Algorithms, these are randomised algorithms with deterministic runtime but may return incorrect answers due to their probabilistic nature.

Always fast and probably correct.