Jan 1, 0001

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

  • $x \in L \implies Pr(M(x) = 1) = 1$
  • $x \not\in L \implies Pr(M(x) = 1) \leq \frac{1}{3}$