Изменения

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

Рассмотрим язык <tex>L \in \mathrm{\Pi_2}</tex>, : <tex>L = \exists p \in poly, \phi \in \mathrm{\widetilde{P}}, \forall x | \in L \Leftrightarrow \forall y_1 . y \ \exists y_2 z : |y|,|z| \le p(|x|), \phi(x, y_1y, y_2z)\}= 1</tex>.<br>Для фиксированного <tex>x</tex> <tex>\phi</tex>Рассмотрим семейство схем можно рассматривать как формулу с <tex>С_n^1...C_n^n</tex>из леммы. битовыми переменными (так как мы знаем, что <tex>\phi \in \mathrm{\widetilde{P}}</tex>, а <tex>\mathrm{P} \subset \mathrm{P}/poly</tex>), где <brtex> Используем выходы схем n</tex>C_n^1...C_n^{i{--1-}}полином от длины входа <tex>x</tex> как вход (из-за ограничений накладываемых по определению класса <tex>b_1...b_\mathrm{i-1\Pi_2}</tex> схемы на <tex>|y|, |z|)</tex>C_n^i.Для заданных <tex>x</tex> и <tex>y</tex> научимся находить такой <tex>z</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_nC_{p(\phi, |x, y_1|)}</tex> и возвращающую на <tex>\phi_{xy}</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_{p(|x|)}(\phi, x, y_1phi_{xy}))= 1\}</tex>. <br> Покажем что Рассмотрим язык <tex>(L_1 = \{x\bigm|\exists G \ \forall y_1 y \ \phi(x, y_1y, C_nG(\phi, x, y_1)phi_{xy}))= 1\}</tex>. <br>Покажем, что <tex>L=L_1</tex> :*<tex>L \Leftrightarrowsubset L_1</tex> <br>Очевидно. Можно за <tex>(\exists G \forall y_1 \phi</tex> взять <tex>C_{p(|x, y_1, G(\phi, x, y_1)) |)}</tex>. *<tex>L_1 \subset L<br/tex> ОчевидноМы докажем это утверждение, если покажем, что из первого следует второеесли какое-то слово не принадлежит <tex>L</tex>, т.к. то оно не принадлежит и <tex>\exists G = D_nL_1</tex>. <br> Если первое ложно, то <tex>\exists y_1 = y_1^0 . y \ \forall y_2 z \ \phi(x, y_1^0y, y_2z) = 0</tex>, следовательно не существует такого тогда <tex>\nexists G</tex>, что <tex>\ \forall y_1y \ \phi(x, y_1y, G(\phi, x, y_1)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(\phiphi_{xy})) = 1\}</tex>. Следовательно, x<tex>L \in \Sigma_2</tex>. Значит, y_1))<tex>\mathrm{\Pi_2} \subset \mathrm{\Sigma_2}</tex>.<br>Докажем теперь, значит что <tex>\mathrm{\Sigma_2} \subset \mathrm{\Pi_2} </tex>.Рассмотрим язык <tex>L \in \mathrm{\Sigma_2}</tex>: <tex>L \in \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>\mathrm{\Sigma_2} \subset \mathrm{\Pi_2} </tex>.Итого, <tex>\mathrm{\Sigma_2} = \mathrm{\Pi_2} </tex>.