Изменения

|statement= Пусть <tex>\mathrm{SAT} \in \mathrm{P}/poly </tex>. Тогда существует такое семейство схем полиномиального размера, что для любой входной функции формулы <tex>\phi</tex> возвращается последовательность бит, удовлетворяющая <tex>\phi</tex>, если она существует, или же последовательность нулей в другом случае.

Пусть нам дана функция формула <tex>\phi</tex> с <tex>n</tex> переменными.<br>Определим Попобуем построить схемы <tex>C_n^1, \ldots, C_n^n</tex> , работающие следующим образом:

Задача определения возврщаемого возвращаемого значения таких схем {{---}} задача тогда будет эквивалентна задаче <tex>\mathrm{SAT}</tex>. По условию <tex>\mathrm{SAT} \in \mathrm{P}/poly </tex>, следовательно, такие схемы существуют и каждая из них будет полиномиального размера. Рассмотрим последовательность: <tex>b_1=C_n^1(\phi), b_2=C_n^2(\phi, b1), \ldots, b_n=C_n^n(\phi, b_1, \ldots, b_{n-1})</tex>. Очевидно, что это будет последовательностью бит, которая удовлетворит <tex>\phi</tex>, или же последовательностью нулей, если <tex>\phi</tex> удовлетворить нельзя. Если при <tex>b_1=1</tex> формулу <tex>\phi</tex> удовлетворить возможно, ее и то есть <tex>C_n^1(\phi)=1</tex>, то нужно вернутьвзять <tex>b_1=1</tex>, если же нет, если <tex>C_n^1(\phi)=0</tex>, тогда имеет смысл искать следующие биты последовательности, удовлетворяющей <tex>\phi</tex> только при <tex>b_1=0</tex>. Следующие биты последовательности выбираются по аналогии. В итоге мы получили <br>За <tex>C_n</tex> обозначим схему , строящую описанным алгоритмом требуемую последовательность. Очевидно, что она будет полиномиального размера (как совокупность <tex>n</tex> схем полиномиального размера). Это и есть требуемая схема для <tex>C_n(\phi)</tex>.

Рассмотрим язык <tex>L \in \mathrm{\Pi_2}</tex>, <tex>L = \{x \bigm| \forall y \ \exists z : |y|,|z| \le p(|x|), p \ in poly, \phi(x, y, z)\}</tex>.<br>Для фиксированного <tex>x</tex> <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_mC_{p(|x|)}</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_mC_{p(|x|)}(\phi_{xy}))\}</tex>.<br>

Очевидно. Можно за <tex>G</tex> взять <tex>C_mC_{p(|x|)}</tex>.