Изменения

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

Если Пусть нам дана формула <tex>\phi</tex> не содержит переменныхс <tex>n</tex> переменными.<br>Попробуем построить схемы <tex>C_n^1, то есть является тождественной единицей\ldots, C_n^n</tex>, решение задачи тривиально.работающие следующим образом:Иначе*<tex>C_n^1(\phi) = 1 \Leftrightarrow \exists x_2, выберем любую переменную \ldots, x_n: \phi(1,x_2, \ldots, x_n)=1</tex>x;*<tex> \ldots </tex> из формулы *<tex>C_n^i(\phi, b_1, \ldots, b_{i-1}) = 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> \ldots </tex>*<tex>x C_n^n(\phi, b_1, \ldots, b_{n - 1}) = 01 \Leftrightarrow \phi(b_1, \ldots, b_{n-1}, 1)=1</tex>. Получим формулу Задача определения возвращаемого значения таких схем тогда будет эквивалентна задаче <tex>\phi_0mathrm{SAT}</tex>. Если По условию <tex>\phi_0 mathrm{SAT} \in SAT\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>x 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>\phi</tex>.

Если <tex>\mathrm{NP } \subset \mathrm{P}/poly</tex>, то <tex>\Sigma_2 = \Pi_2</tex>.

Так Рассмотрим язык <tex>L \in \mathrm{\Pi_2}</tex>: <tex> \exists p \in poly, \phi \in \mathrm{\widetilde{P}}, \forall x \in L \Leftrightarrow \forall y \ \exists z : |y|,|z| \le p(|x|), \phi(x, y, z) = 1</tex>.<br>Для фиксированного <tex>x</tex> <tex>\phi</tex> можно рассматривать как формулу с <tex>n</tex> битовыми переменными (так как мы знаем, что <tex>\phi \in \mathrm{\widetilde{P}}</tex>, а <tex>NP \mathrm{P} \subset \mathrm{P}/poly</tex>), то для любого где <tex>n</tex> найдётся схема полиномиального размера {{---}} полином от длины входа <tex> C_nx</tex>, такая что (из-за ограничений накладываемых по определению класса <tex>C_\mathrm{\Pi_2}</tex> на <tex>|xy|, |z|}(x) = \left[x \in SAT\right]</tex>.Тогда, найдётся Для заданных <tex>x</tex> и схема полиномиального размера <tex> D_ny</tex> научимся находить такой <tex>z</tex>, выдающая для что <tex>\phi(x \in SAT,y,z)=1</tex> набор значений, удовлетворяющий формулеесли это возможно.Подставим значения <tex>x</tex> и <tex>y<br/tex>Рассмотрим язык в формулу <tex>L \in phi</tex>. Теперь <tex>\Pi_2phi</tex> зависит только от <tex>z</tex>, : <tex>L = \phi_{xy}(z:\forall x )</tex> .Из предыдущей леммы мы установили существования семейство схем полиномиального размера <tex>C_1, \exists y ldots, C_n, \ldots </tex> Запустим схему <tex> \phiC_{p(|x, y, z|)}</tex> на <tex>\phi_{xy}</tex>.Эта схема вернет нам такое значение <tex>z<br/tex>Рассмотрим формулу , что <tex>\exists phi(x,y,z)=1</tex> , если <tex>\phi(x, y, z)</tex> как экземпляр задачи удовлетворима для заданных <tex>x</tex> и <tex>SATy</tex>, или же последовательность нулей.<br/>Тогда определение языка <tex>L</tex> можно переписать так: <tex>L=\{z: x \bigm| \forall x</tex> <tex> y \ \phi(x,D_y, C_{p(|zx|)}(x, z\phi_{xy}), z)= 1\}</tex>.<br/>Покажем что Рассмотрим язык <tex>L_1 = \{x\bigm|\exists G \ \forall x</tex> <tex> y \ \phi(x,D_y, G(\phi_{|z|xy}(x, z), z)= 1\}</tex> . <br>Покажем, что <tex>\LeftrightarrowL=L_1</tex> :*<tex>L \exists Dsubset L_1</tex> <br>Очевидно. Можно за <tex> \forall xG</tex> взять <tex>\phiC_{p(|x, D(x, z), z|)}</tex>.Очевидно, из первого следует второе, так как *<tex>L_1 \exists D = D_{|z|}subset L</tex>.Если первое ложноМы докажем это утверждение, если покажем, что если какое-то слово не принадлежит <tex>\exists xL</tex>, то оно не принадлежит и <tex>\forall yL_1</tex> .<br>Если <tex>\exists y \ \forall z \ \phi(x, y, z) = 0</tex>, а значит тогда <tex>\nexists G \ \forall D y \ \phi (x, D_y, G(\phi_{xy}))=1</tex>. <br>Таким образом <tex>L =\{x\bigm|\exists G, |zG|}< p(|x|) \ \forall y, z|y|<p(|x|)\ \phi(x, zy, G(\phi_{xy}))= 1\}</tex>. Следовательно, <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 DSigma_2}</tex> : <tex>L \forall xin \mathrm{\Sigma_2} \Rightarrow \overline{L} \in \mathrm{\Pi_2} \Rightarrow \overline{L} \in \mathrm{\Sigma_2} \Rightarrow L \in \mathrm{\Pi_2}</tex> . Получается, что <tex>\phi(x, D(x, z), z)mathrm{\Sigma_2} \subset \mathrm{\Pi_2}</tex>.Итого, значит <tex>L \in mathrm{\Sigma_2} = \mathrm{\Pi_2} </tex>.