109
правок
Изменения
м
→Доказательство
Из того, что класс <tex>\mathrm{BPP}</tex> замкнут относительно дополнения и <tex>\mathrm{co}\Sigma_2 = \Pi_2</tex> следует, что достаточно доказать включение <tex>\mathrm{BPP} \subset \Sigma_2</tex>.
<tex>\mathrm{BPP}</tex> можно определить, как множество таких языков <tex>L</tex>, что <tex>x \in L \Leftrightarrow \exists</tex> «много» вероятностных лент <tex>y: R(x,y)</tex>. <tex>\Sigma_2</tex> определяется, как множество <tex>\{ L \mid x \in L \Leftrightarrow \exists y \forall z R(x, y, z)\}</tex>. Таким образом, необходимо уметь записывать <tex>\exists</tex> «много» с помощью квантора кванторов <tex>\exists\forall</tex>.
Рассмотрим язык <tex>G</tex> всех слов длины <tex>k</tex> над алфавитом <tex>\{0, 1\}</tex>, для некоторого <tex>k</tex>, значение которого будет получено позже. Определим операцию <tex>\oplus</tex> над славами из этого языка, как побитовое исключающее или.
