Изменения

Рассмотрим язык <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>n</tex> {{---}} полином от длины входа (из-за ограничений накладываемых по определению класса <tex>\mathrm{\Pi_2}</tex> на <tex>|y|, |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>

Тогда определение языка <tex>L</tex> можно переписать: <tex>L = \{x \bigm| \forall y \ \phi(x, y, C_m(\phi_{xy}))\}</tex>.<br>