Изменения
Нет описания правки
| proof =
Из того, что класс <tex>\mathrm{BPP}</tex> замкнут относительно дополнения и <tex>\mathrm{co}\Sigma_2 } = \mathrm{\Pi_2}</tex>, следует, что достаточно доказать включение <tex>\mathrm{BPP} \subset \mathrm{\Sigma_2}</tex>.
<tex>\mathrm{BPP}</tex> можно определить как множество таких языков <tex>L</tex>, что <tex>x \in L \Leftrightarrow</tex> существует «много» таких вероятностных лент <tex>y</tex>, что <tex>R(x,y)</tex>. <tex>\mathrm{\Sigma_2}</tex> — множество таких языков <tex>L</tex>, что <tex>x \in L \Leftrightarrow</tex> существует такой <tex>y</tex>, что для любого <tex>z</tex> <tex>R(x, y, z)</tex>. Таким образом, необходимо уметь записывать «существует много» с помощью кванторов <tex>\exists\forall</tex>.
