Изменения

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

Зададимся формулой Пусть нам дана формула <tex>\phi</tex>с <tex>n</tex> переменными. Определим семейство схем <br>Попробуем построить схемы <tex>C_n^1 ... , \ldots, C_n^n</tex> так, работающие следующим образом: схема *<tex>C_n^i1(\phi) = 1 \Leftrightarrow \exists x_2,\ldots, x_n: \phi(1,x_2, \ldots, x_n)=1</tex> будет принимать на вход формулу ;*<tex>\phildots </tex> и *<tex>C_n^i(\phi, b_1, \ldots, b_{i-1</tex> бит <tex>}) = 1 \Leftrightarrow \exists x_{i+1},\ldots, x_n: \phi(b_1 ... , \ldots, b_{i-1},1,x_{i+1}, \ldots, x_n)=1</tex>, и возвращать ;*<tex>1\ldots </tex> тогда и только тогда, когда существует набор переменных, удовлетворяющий *<tex>C_n^n(\phi</tex>, такой что <tex>x_1 = b_1 ... x_, \ldots, b_{in -1}) =1 \Leftrightarrow \phi(b_1, \ldots, b_{in-1}, 1)=1</tex> и .Задача определения возвращаемого значения таких схем тогда будет эквивалентна задаче <tex>x_i=1\mathrm{SAT}</tex>. Так как задача определения выходного значения таких схем принадлежит По условию <tex>NP\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^i1(\phi)=1</tex> вернет значение , то нужно взять <tex>ib_1=1</tex>-й переменной удовлетворяющего набора, в противном случае схема вернет если же нет, если <tex>C_n^1(\phi)=0</tex>. Теперь используем выходы схем , тогда имеет смысл искать следующие биты последовательности, удовлетворяющей <tex>C_n^1...C_n^{i-1}\phi</tex> как вход только при <tex>b_1=0</tex>.Следующие биты последовательности выбираются по аналогии..b_{i-1}<br>За <tex>C_n</tex> схемы обозначим схему, строящую описанным алгоритмом требуемую последовательность. Очевидно, что она будет полиномиального размера (как совокупность <tex>C_n^in</tex> схем полиномиального размера). Это и получим схему с есть требуемая схема для <tex>n\phi</tex> выходами, возвращающую требуемые набор.

Так как Рассмотрим язык <tex>L \in \mathrm{NP\Pi_2} </tex>: <tex> \exists p \in poly, \subset phi \in \mathrm{\widetilde{P}}, \forall x \in L \Leftrightarrow \forall y \ \exists z : |y|,|z| \le p(|x|), \phi(x, y, z) = 1</polytex>.<br>Для фиксированного <tex>x</tex> <tex>\phi</tex> можно рассматривать как формулу с <tex>n</tex>битовыми переменными (так как мы знаем, то что <tex>SAT \phi \in \mathrm{\widetilde{P}}</tex>, а <tex>\mathrm{P} \subset \mathrm{P}/poly</tex>. Тогда ), где <tex>n</tex> {{---}} полином от длины входа <tex>x</tex> (из-за ограничений накладываемых по лемме найдётся семейство схем полиномиального размера определению класса <tex> D_n\mathrm{\Pi_2}</tex> такихна <tex>|y|, что для любой формулы |z|)</tex>.Для заданных <tex>x</tex> и <tex>y</tex> научимся находить такой <tex>\phi \in SATz</tex>, что <tex>D_{|\phi|}(\phix,y,z)=1</tex> выводит набор значений, удовлетворяющий если это возможно. Подставим значения <tex>x</tex> и <tex>y</tex> в формулу <tex>\phi</tex>. Рассмотрим язык Теперь <tex>L \in \Pi_2phi</tex> зависит только от <tex>z</tex>, : <tex>L = \phi_{xy}(z | \forall x )</tex> .Из предыдущей леммы мы установили существования семейство схем полиномиального размера <tex>C_1, \ldots, C_n, \exists y ldots </tex> Запустим схему <tex> \phiC_{p(|x, y, z|)}</tex> на <tex>\phi_{xy}</tex>.Эта схема вернет нам такое значение <tex>z<br/tex>Рассмотрим формулу , что <tex>\psiphi(x,y, z) = \exists y1</tex> , если <tex>\phi(x, y, z)</tex> как экземпляр задачи удовлетворима для заданных <tex>x</tex>SATи <tex>y</tex>, или же последовательность нулей.<br/>Тогда определение языка <tex>L</tex> можно переписать так: <tex>L=\{z x \bigm| \forall x</tex> <tex> y \ \phi(x,D_y, C_{p(|\psi(x, z|)|}(\psi(x, zphi_{xy})), z)= 1\}</tex>.<br/>Покажем что Рассмотрим язык <tex>(L_1 = \{x\bigm|\exists G \ \forall x</tex> <tex> y \ \phi(x,D_{|\psi(xy, z)|}G(\psi(x, zphi_{xy})), z)= 1\}</tex> . <br>Покажем, что <tex>)\LeftrightarrowL=L_1</tex> :*<tex>(L \exists G : subset L_1</tex> <br>Очевидно. Можно за <tex> \forall xG</tex> взять <tex>\phiC_{p(|x, G(\psi(x, z)), z)|)}</tex>.<br>Очевидно, из первого следует второе, так как *<tex>L_1 \exists G = D_{|\psi(x, z)|}subset L</tex>.Если первое ложноМы докажем это утверждение, если покажем, что если какое-то слово не принадлежит <tex>\exists x = x_0 : L</tex> , то оно не принадлежит и <tex>\forall yL_1</tex> .<br>Если <tex>\exists y \ \forall z \ \phi(x, y, z) = 0</tex>, а значит тогда <tex>\nexists G \ \forall y \ \phi(x, y, G (\phi_{xy}))=1</tex> . <br>Таким образом <tex>L =\{x\bigm|\exists G, |G| < p(|x = x_0 : |) \ \forall y, |y|<p(|x|) \ \phi (x, y, G(\psi(x, zphi_{xy}))= 1\}</tex>. Следовательно, z)<tex>L \in \Sigma_2</tex>. Значит, то есть второе ложно<tex>\mathrm{\Pi_2} \subset \mathrm{\Sigma_2} </tex>.<br>ИтогоДокажем теперь, что <tex>\mathrm{\Sigma_2} \subset \mathrm{\Pi_2} </tex>.Рассмотрим язык <tex>L=\in \mathrm{z | \exists G : Sigma_2}</tex> : <tex>L \in \mathrm{\Sigma_2} \Rightarrow \overline{L} \in \mathrm{\forall xPi_2} \Rightarrow \overline{L} \in \mathrm{\Sigma_2} \Rightarrow L \in \mathrm{\Pi_2}</tex> . Получается, что <tex>\phi(x, G(mathrm{\Sigma_2} \subset \psi(x, z)), z)mathrm{\Pi_2}</tex>.Итого, значит <tex>L \in mathrm{\Sigma_2} = \mathrm{\Pi_2} </tex>.