Изменения

|statement= Пусть <tex>\mathrm{SAT} \in \mathrm{P}/poly </tex>. Тогда для любой формулы <tex>\phi</tex> с <tex>n</tex> переменными существует такая последовательность такое семейство схем полиномиального размера <tex>C_n^1, \ldots, C_n^n</tex>, что для любой входной функции <tex>C_n^i\phi</tex> возвращает значение <tex>i</tex>-й переменной в наборе переменныхвозвращается последовательность бит, удовлетворяющих удовлетворяющая <tex>\phi</tex>, если <tex>\phi \in \mathrm{SAT}</tex>она существует, или <tex>0</tex> если <tex>\phi \not \in \mathrm{SAT}</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>C_n(\phi)</tex>.

Рассмотрим язык <tex>L \in \mathrm{\Pi_2}</tex>, <tex>L = \{x \bigm| \forall y_1 . y \ \exists y_2 z \ \phi(x, y_1y, y_2z)\}</tex>.<br/>Рассмотрим семейство схем <tex>C_n^1, \ldotsphi</tex> можно рассмтривать как функцию с <tex>n</tex> битовыми переменныии, C_n^где <tex>n</tex> {{---}} полином от длины входа (из леммы. <br> Используем выходы схем -за ограничений накладываемых по определению класса <tex>C_n^1, \ldots, C_n^mathrm{i-1\Pi_2}</tex> как вход на <tex>b_1|y|, \ldots, b_{i-1}|z|)</tex>.Для заданных <tex>x</tex> и <tex>y</tex> схемы найдем такой <tex>C_n^iz</tex>, при этом заменяя те схемы что <tex>C_n^i\phi(x,y,z)=1</tex>, которые возвращают если это возможно. Подставим значения переменных <tex>x</tex> и <tex>y_1y</tex> в функцию <tex>\phi</tex>. Теперь <tex>\phi</tex> зависит только от <tex>z</tex>: <tex>\phi_{xy}(z)</tex> на простые входы. Из предыдущей леммы мы получили семейство схем полиномиального размера <brtex> ИтогоC_1, получим \ldots, C_n, \ldots </tex> Запустим схему <tex>C_n(C_m</tex> на <tex>\phiphi_{xy}</tex>, где <tex>m=n-|x, y_1)|-|y|</tex> и возвращающую . Эта схема вернет нам такое значение <tex>y_2z</tex>, что <tex> \phi(x, y_1y, y_2z) = 1</tex>, если <tex>\phi(x, y_1y, y_2z)</tex> удовлетворима для заданных <tex>x, y_1</tex>и <tex>y</tex>, или же последовательность нулей. <br> Теперь Тогда определение языка <tex>L</tex> можно переписать так: <tex>L = \{x \bigm| \forall y_1 y \ \phi(x, y_1y, C_nC_m(\phi, x, y_1phi_{xy}))\}</tex>. <br> Покажем что Рассмотрим язык <tex>(L_1 = \{x\bigm|\exists G \ \forall y_1 y \ \phi(x, y_1y, C_nG(\phix, xy , y_1)\phi_{xy}))\}</tex> . <br>Покажем, что <tex>\LeftrightarrowL=L_1</tex> :*<tex>(\exists G . \forall y_1 \phi(x, y_1, G(L \phi, x, y_1)) )subset L_1</tex>. <br> Очевидно, что из первого следует второе, т.к. Можно за <tex>\exists G = C_n</tex>. взять <brtex> Если первое ложно, то C_m</tex>\exists y_1 = y_1^0 . *<tex>L_1 \forall y_2 \phi(xsubset L</tex>Мы докажем это утверждение, y_1^0если покажем, y_2) = 0что если какое-то слово не принадлежит <tex>L</tex>, следовательно то оно не существует такого принадлежит и <tex>GL_1</tex>, что .<br>Пусть <tex>\exists y \ \forall y_1z \ \phi(x, y_1y, z)=0 \Rightarrow \nexists G(\ \forall y \ \phi(x, xy, y_1)G(\phi_{xy}) )=1</tex>{{---}} очевидно. <br>Теперь определение исходного языка можно записать как Таким образом <tex>L = \{x \bigm| \exists G . , |G| < p(|x|) \ \forall y_1 y, |y|<p(|x|) \ \phi(x, y_1y, G(\phix, xy , y_1\phi_{xy}))\}</tex>. Следовательно, значит <tex>L \in \Sigma_2</tex>.