Изменения
→Доказательство
* <tex>P(\exists y \in G \bigwedge_{i=1}^{k} y \not \in g_i \oplus X) = |G|\left(1 - \frac{|X|}{|G|}\right)^k</tex>.
Если <tex>|G|\left(1 - \frac{|X|}{|G|}\right)^k < 1</tex>, то существует набор <tex>\{g_i\}</tex>, что для любого <tex>y</tex> выполнено <tex>\bigwedge_bigvee_{i=1}^{k} y \not \in g_i \oplus X</tex>, а из этого следует, что <tex>X</tex> большой.
Рассмотрим язык <tex>L \in \mathrm{BPP}</tex>. Не уменьшая общности, можем считать, что программа <tex>M</tex>, распознающая этот язык, завершается за <tex>p(|x|)</tex> шагов и вероятность ошибки не превосходит
* <tex>\frac{|X|}{|G|} \geqslant 1 - \frac1{3k}</tex>;
* <tex>1 - \frac{|X|}{|G|} \leqslant \frac1{3k}</tex>;
* <tex>|G|\left(1 - \frac{|X|}{|G|}\right)^k \leqslant |G| \left(\frac1{3k}\right)^k = \left(\frac2{3k}^k \right) < 1</tex>, что влечет за собой то, что <tex>X</tex> большой.
Если <tex>x \not \inL</tex>, то <tex>\frac{|X|}{|G|} \leqslant \frac1{3k} < \frac1k</tex>, а, следовательно, <tex>X</tex> не является большим.
Таким образом, <tex>x \in L \Leftrightarrow \exists k, g_1, g_2, \dots, g_k \forall y \bigvee_{i=1}^{m} y \in g_i \oplus X</tex>, то есть
<tex>x \in L \Leftrightarrow \exists k, g_1, g_2, \dots, g_k \forall y \bigvee_{i=1}^{m} M(x, y \oplus g_i)</tex>,
а, значит, <tex>L \in \Sigma_2</tex>, <tex>\mathrm{BPP} \subset \Sigma_2</tex> и <tex>\mathrm{BPP} \subset \Sigma_2 \cap \Pi_2</tex>, что и требовалось доказать.
