Изменения
→Доказательство
Если <tex>x \not \in L</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}^{mk} 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}^{k} y \oplus g_i \in X</tex>, то есть<tex>x \in L \Leftrightarrow \exists k, g_1, g_2, \dots, g_k \forall y \bigvee_{i=1}^{mk} 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>, что и требовалось доказать.
