109
правок
Изменения
→Доказательство
Рассмотрим язык <tex>L \in \mathrm{BPP}</tex>.
<tex>X_x = \{y \mid M(x,y) = 1\}</tex>
<tex>x \in L \Rightarrow \frac{|X_x|}{|G|} \geqslant 1 - \varepsilon</tex>
<tex>x \not \in L \Rightarrow \frac{|X_x|}{|G|} \leqslant \varepsilon</tex>
