Изменения

Рассмотрим язык <tex>L \in \mathrm{\Pi_2}</tex>, : <tex>L = \exists p \in poly, \phi \in \mathrm{\widetilde{P}}, \forall x \in L \bigm| Leftrightarrow \forall y \ \exists z : |y|,|z| \le p(|x|), p \in poly, \phi(x, y, z)\}= 1</tex>.<br>Для фиксированного <tex>x</tex> <tex>\phi</tex> можно рассмтривать рассматривать как формулу с <tex>n</tex> битовыми переменныии переменными (так как мы знаем, что <tex>\phi \in \mathrm{\widetilde{P}}</tex>, а <tex>\mathrm{P} \subset \mathrm{P}/poly</tex>), где <tex>n</tex> {{---}} полином от длины входа <tex>x</tex> (из-за ограничений накладываемых по определению класса <tex>\mathrm{\Pi_2}</tex> на <tex>|y|, |z|)</tex>.

Из предыдущей леммы мы установили существования семейство схем полиномиального размера <tex>C_1, \ldots, C_n, \ldots </tex> Запустим схему <tex>C_{p(|x|)}</tex> на <tex>\phi_{xy}</tex>. Эта схема вернет нам такое значение <tex>z</tex>, что <tex>\phi(x,y,z)=1</tex>, если <tex>\phi(x,y,z)</tex> удовлетворима для заданных <tex>x</tex> и <tex>y</tex>, или же последовательность нулей. <br>Тогда определение языка <tex>L</tex> можно переписать: <tex>L = \{x \bigm| \forall y \ \phi(x, y, C_{p(|x|)}(\phi_{xy}))= 1\}</tex>.<br>Рассмотрим язык <tex>L_1 = \{x\bigm|\exists G \ \forall y \ \phi(x, y, G(\phi_{xy}))= 1\}</tex>. <br>

Пусть Если <tex>\exists y \ \forall z \ \phi(x,y,z)=0 \Rightarrow </tex>, тогда <tex>\nexists G \ \forall y \ \phi(x, y, G(\phi_{xy}))=1</tex> {{---}} очевидно.<br>Таким образом <tex>L =\{x\bigm|\exists G, |G| < p(|x|) \ \forall y, |y|<p(|x|) \ \phi(x, y, G(\phi_{xy}))= 1\}</tex>. Следовательно, <tex>L \in \Sigma_2</tex>.