PP

$L \in RP \iff$ существует полиномиальная ВМТ:

• $x \in L \implies Pr(M(x) = 1) \geq \frac{1}{2}$
• $x \not\in L \implies Pr(M(x) = 1) < \frac{1}{2}$

Важно, чтобы не свелось к подбрасыванию монетки