109
правок
Изменения
м
→Доказательство
Если <tex>x \not \in</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>L \in \Sigma_2</tex>, <tex>\mathrm{BPP} \subset \Sigma_2</tex> и <tex>\mathrm{BPP} \subset \Sigma_2 \cap \Pi_2</tex>, что и требовалось доказать.
