Изменения
Нет описания правки
Таким образом, <tex>x \in L \Leftrightarrow \exists \{g_i\}_{i=1}^{k} \forall y \bigvee\limits_{i=1}^{k} y \in g_i \oplus A_x</tex>, то есть <tex>x \in L \Leftrightarrow \exists \{g_i\}_{i=1}^{k} \forall y \bigvee\limits_{i=1}^{k} y \oplus g_i \in A_x</tex>, то есть
<tex>x \in L \Leftrightarrow \exists \{g_i\}_{i=1}^{k} \forall y \bigvee\limits_{i=1}^{k} 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>, что и требовалось доказать.
}}
