Изменения
Нет описания правки
|proof=
Рассмотрим язык <tex>L \in \mathrm{\Pi_2}</tex>, <tex>L = \{x \bigm| \forall y \ \exists z \ \phi(x, y, z)\}</tex>.<br>
<tex>\phi</tex> можно рассмтривать как функцию с <tex>n</tex> битовыми переменныии(так как мы знаем, что <tex>\phi \in \mathrm{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>x</tex> и <tex>y</tex> научимся находить такой <tex>z</tex>, что <tex>\phi(x,y,z)=1</tex>, если это возможно. Подставим значения <tex>x</tex> и <tex>y</tex> в функцию <tex>\phi</tex>. Теперь <tex>\phi</tex> зависит только от <tex>z</tex>: <tex>\phi_{xy}(z)</tex>.
Из предыдущей леммы мы получили семейство схем полиномиального размера <tex>C_1, \ldots, C_n, \ldots </tex> Запустим схему <tex>C_m</tex> на <tex>\phi_{xy}</tex>, где <tex>m=n-|x|-|y|</tex>. Эта схема вернет нам такое значение <tex>z</tex>, что <tex>\phi(x,y,z)=1</tex>, если <tex>\phi(x,y,z)</tex> удовлетворима для заданных <tex>x</tex> и <tex>y</tex>, или же последовательность нулей. <br>
