Изменения

Если <math>NP \subset P/poly</math> то <math>\Sigma_2=\Pi_2</math>

Пусть есть логические схемы для <tex>NP</tex> (для любой задаче задачи из NP).Например зафиксируем Зафиксируем любую задачу из NP например пусть сат разрешает логическими схемами <tex>SAT : C_1...C_n...NP</tex>, сат который поддерживается с одним битом разрешается логической схемой с1 сат с двумя переменными логической схемой с2...Что значит разрешается? Это значит что логическая схема, в инпуте которой который каким то логичным образом закодирована формула, а на выходе логичным образом в вмде 0 и один закодировано есть ли доказательство(разложение) или нет. И причем размер этой логической схемы не больше чем какой то полином от n. Но мы не утверждаем, что можем как то конструктивно их построить. Если бы мы могли за полином их построить, то это бы означало, что сат2=п2, что P=NP.Итак, что это означает, рассмотрим, это означает на самом деле что для любого n (зафиксируем n) Это означает что для фиксированного <tex>n</tex> <tex>\exists{}</tex> такая логическая схема <tex>C_n</tex>, что Например пусть <tex>\forall{} формулы \varphi{} (\varphi{} \in{} SAT |\varphi{}|=n \Leftrightarrow C_n(\varphi{})=1)</tex>  разрешается логическими схемами <tex> \exists{C_1...C_n} \forall{\varphi{}} (\forall{x} формулы длины n \varphi{(x)}=0 \Leftrightarrow C_n(\varphi{})=0)</tex>. Рассмотрим язык <tex>L\in \Pi_2</tex>. Это означает, что <tex>x\in L \Leftrightarrow \forall{y} \exists{z}: \psi{(x,y,x)}. </tex>Что такое существует z что пси от х игрик z? Обозначим пары <x,y>, для которых такой z существует как какой нибудь язык L1 Рассмотрим <tex>L_1 = \{<x,y>|\exists{z}: \psi{(x,y,z)}\}</tex>. Заметим что <tex>L_1 \in NP</tex> по определению <tex>NP</tex>Итого L это множество слов <tex>L={x|\forall{y} <x,y>\in{L_1}}</tex>Нужно доказать что <tex>L\in \Sigma_1</tex> Что такое <x,y> \in L1 ?Если <tex>L_1\in{} NP \Rightarrow тоL_1 \le{}_m SAT</tex> по карпу с помощью одним битом разрешается логической схемой <tex>fC_1</tex>, т.е. <tex>L=\{x|\forall{y} f(<x,y>)\in{SAT}\}</tex> Что такое f(<x,y>)\in SAT ?с двумя переменными логической схемой <tex>f(<x,y>)\in{SAT}C_2</tex> - это значит, что для некоторого набора булевых(логических) схем, выполнимость всего этого набора, если предположить, что набор этих схем нам известен то получится что <tex>L=\{x|\forall{y} C_n(f(<x,y>))=1\}</tex> где n- длина входа <x,y>Нам надо откуда то взять этот набор. Мы можем его угадать используя квантор существует снаружи.Cn он существует по предположению что NP входит в P/poly и т.ед.<tex>L=\{x|\exists{C_n}: C_n решает SAT и \forall{y} C_n(f(<x,y>))=1\}</tex> Что такое Cn Решает SAT? Нам разрешается использовать только квантор для любого.<tex>C_n</tex> решает <tex>SAT</tex> <tex>\Leftrightarrow</tex> если <tex>\forall{\varphi} \forall{x} (fi(x)=1 \Rightarrow C_n(fi)=1)</tex>     

'''Требуется доказать, что <tex> L\exists{C_n} in \forall{\varphi{}} (\forall{x} \varphi{(x)}=0 \Leftrightarrow C_n(\varphi{})=0)Sigma_1</tex>.'''

Рассмотрим язык Если <tex>LL_1\in {} NP</tex> то <tex>L_1 \Pi_2le{}_m SAT</tex> с помощью <tex>f</tex>, т. Это означает, что е. <tex>x\in L =\Leftrightarrow {x|\forall{y} \exists{z}: \psi{f(<x,y,x>)\in{SAT}\}</tex>

Но надо откуда-то взять этот набор. Можно его угадать, используя квантор существует. Добавим его.Так как '''Что такое <tex>NP \subset P/polyC_n</tex> то Решает <tex>L=\{x|\exists{C_n}: C_n решает SAT и \forall{y} C_n(f(<x,y>))=1\}</tex>?'''

Что означает Запишем это используя квантор "<tex>C_n\forall{}</tex> решает <tex>SAT</tex>? Нужно переписать с квантором для любого".

Воспользуемся самосведением <tex>SAT</tex>: <tex>L=\{x|\exists{C1,C2,..,Cn} - набор логических схем для SAT и\forall{y} C_n(f(<x,y>))=1\}</tex>,где - <tex>C1,C2,..,Cn</tex> набор логических схем для <tex>SAT</tex>.

Если <tex>C</tex> решает <tex>\forall{\varphi{}} (C_{|\varphi{}|}(\varphi{})=0 \Rightarrow \forall{x} \varphi(x)=0) (C_{|\varphi{}|}(\varphi{})=1 \Rightarrow \varphi{}|_{x_1=0} \in SAT или </tex> то все хорошо. Если нет, то зафиксируем формулу <tex>\varphi{}|_{x_1=1} \in SAT)_0</tex>, которую он не решает. Если на этой формуле выдаст 0, а должна выдать 1, то получается что не удовлетворяет первую часть предыдущего выражения и, значит, не будет работать. Если наоборот выдаст 1 а на самом деле формула не удавлетворима то обе скобки не выполнятся и опять формула работать не будет.

Если <tex>C</tex> решает <tex>SAT</tex> то все хорошоРассмотрим минимальную неправильную схему. Тогда на той формуле, если нет то зафиксируем формулу на которой не решаетэта схема неправильна, по предположению, что все более короткие формулы правильны,эта формула распознается схемами с меньшим числом входов. Если выдаст Поэтому обе скобки будут 0 а должна выдать 1 то первую и мы не удолветворяет, если наоборот то обе не удовлетворяетузнаем набор схем. Развернем формулу до конца.

<tex> \forall{\varphi{}}: |\varphi{}|=m \forall{x_1}..\forall{x_m} если </tex><tex> C_m(\varphi{})=0 \Rightarrow \varphi{(x_1)}=0 </tex> иначе <tex> C_{m-1}(\varphi|_{x_1=0})=0 \Rightarrow \varphi|_{x_1=0}(x_2)=0</tex> <tex>C_{m-1}(\varphi{}|_{x_1=1})=0 \Rightarrow \varphi{}|_{x_1=0}(x_2)=0</tex> <tex>C_{m-1}(\varphi{}|{x_1=0}) \vee{} C_{m-1}(\varphi{}|_{x_1=1})</tex> Далее рекурсивно записываем ту же самую формулу от того из них, которое равно 1.

Получаем что <texmath>C_{m-1}(L\varphi{}|{x_1=0}) in \vee{} C_{m-1}(\varphi{}|_{x_1=1})Sigma_2</texmath>