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> над словами из этого языка как побитовое исключающее или.
* <tex>|G|\left(1 - \frac{|X|}{|G|}\right)^k \leqslant |G| \frac1{3k}^k = \frac2{3k}^k < 1</tex>, что влечет за собой то, что <tex>X</tex> большой.
Если <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>x \in L \Leftrightarrow \exists k, g_1, g_2, \dots, g_k \forall y \bigvee_{i=1}^{m} 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>, что и требовалось доказать.
