Definition. Bounded-error Probabilistic Polynomial Time [BPP]

$L \in \text{BPP}$ (Bounded-error Probabilistic Polytime) if there is a probabilistic Turing machine that, on input $x$, runs in time $\text{poly}\left( |x| \right)$ and has behavior:

• $x \in L$ if the probability of accepting is greater than $\frac{2}{3}$
• $x \in L$ if the probability of rejecting is greater than $\frac{2}{3}$
• ($\frac{2}{3}$ is arbitrary: we just need $\frac{p}{q} > \frac{1}{2}$)

…helpful diagram…