Изменения
Нет описания правки
Выберем <tex>p(n)</tex> так, чтобы <tex>\frac{r(n)}{p(n)} < 2^{p(n)} - 2</tex> и <tex>k = \lceil \frac{r(n)}{p(n)} \rceil + 1</tex>. Получаем <tex>\frac{r(n)}{p(n)} < k < 2^{p(n)}</tex>, то есть <tex>x \in L \Leftrightarrow A_x</tex> — <tex>k</tex>-большое.
Таким образом, <tex>x \in L \Leftrightarrow \exists \{g_i\}_{i=1}^{k} \subset G</tex> : <tex>\forall y \in G</tex> <tex>\left( \bigvee\limits_{i=1}^{k} y \in g_i \oplus A_x\right) </tex>. Заметив, что <tex>y \in g_i \oplus A_x \Leftrightarrow y \oplus g_i \in A_x \Leftrightarrow M(x, y \oplus g_i)</tex>, получаем <tex>L \in \Sigma_2</tex>, <tex>\mathrm{BPP} \subset \mathrm{\Sigma_2}</tex> и <tex>\mathrm{BPP} \subset \mathrm{\Sigma_2} \cap \mathrm{\Pi_2}</tex>.
}}
