Изменения

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

Пусть есть логические схемы для <tex>NP</tex> (для любой задаче задачи из NP).Например зафиксируем Зафиксируем любую задачу из <tex>NP например </tex>. Например пусть сат разрешает <tex>SAT</tex> разрешается логическими схемами <tex>SAT : C_1...C_n...</tex>, сат который поддерживается (<tex>SAT</tex> с одним битом разрешается логической схемой с1 сат <tex>C_1</tex>, <tex>SAT</tex> с двумя переменными логической схемой с2.<tex>C_2</tex> и т.д.Что значит разрешается? Это значит что логическая схема, в инпуте которой который каким то логичным образом закодирована формула, а на выходе логичным образом в вмде 0 и один закодировано есть ли доказательство(разложение) или нет. И причем размер этой логической схемы не больше чем какой то полином от n. Но мы не утверждаем, что можем как то конструктивно их построить. Если бы мы могли за полином их построить, то это бы означало, что сат2=п2, что P=NP.Итак, что это означает, рассмотрим, это означает на самом деле что для любого n (зафиксируем n)

Рассмотрим язык <tex>L\in \Pi_2</tex>. Это означаетзначит что если на вход логической схеме подать каким-то логичным образом закодированную формулу, что то на выходе получется логичным образом в виде 0 и 1 закодированный ответ - имеется разложение или нет. И причем размер этой логической схемы <tex>x\in L \Leftrightarrow \forall{y} \exists{z}: |C_n|\psi{le p(x,y,xn)}</tex>Что такое существует z что пси от х игрик z? Обозначим пары <x,y>, для которых такой z существует как какой нибудь язык L1 Рассмотрим где <tex>L_1 = \{<x,y>|\exists{z}: \psi{p(x,y,zn)}\}</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_1SAT_2=\in{} NP \Rightarrow тоL_1 \le{}_m SATPi_2</tex> по карпу с помощью и значит <tex>fP = NP</tex>, т.е. <tex>L=\{x|\forall{y} f(<x,y>)\in{SAT}\}</tex>

Что такое f(Итак, получается, что если зафиксировать <x,ytex>)\in SAT ?n</tex>f(, то для этого фиксированного <x,ytex>)\in{SAT}n</tex> - это значит, что для некоторого набора булевых(логических) схем, выполнимость всего этого набора, если предположить, что набор этих схем нам известен то получится что будет <tex>L=\exists{C_n}\forall{} формулы \varphi{} (\varphi{} \in{x} SAT |\forallvarphi{y} |=n \Leftrightarrow C_n(f(<x,y>)\varphi{})=1\})</tex> где n- длина входа <x,y>Нам надо откуда то взять этот набор. Мы можем его угадать используя квантор существует снаружи.Cn он существует по предположению что NP входит в P/poly т.е. <tex>L=\{x|\exists{C_n}: C_n решает SAT и \forall{y\varphi{}} C_n(f\forall{x} \varphi{(<x,y>))}=10 \Leftrightarrow C_n(\varphi{})=0)</tex>, где <tex>x</tex> - вход длины <tex>n</tex>

Что такое Cn Решает SAT? Нам разрешается использовать только квантор для любого.<tex>C_n</tex> решает <tex>SAT</tex> Рассмотрим язык <tex>L\in \LeftrightarrowPi_2</tex> если . Это означает, что <tex>x\forall{in L \varphi} Leftrightarrow \forall{xy} (fi(x)=1 \Rightarrow C_n(fi)=1)</tex> Воспользуемся самосведением <tex>SAT</tex>: <tex>L=\{x|\exists{C1,C2,..,Cnz} - набор логических схем для SAT и: \forallpsi{y} C_n(f(<x,y>),x)=1\}</tex>Внутри будем проверять используемый набор

Если '''Что такое <tex>C\exists{z}:\psi{(x,y,z)}</tex> решает <tex>SAT</tex> то все хорошо, если нет то зафиксируем формулу которую он не решает. Если выдаст 0 а должна выдать 1 то вот эту первую часть не удолветворяет и тут не будет работать, если наоборот выдаст 1 а на самом деле формула не удавлетворима то ни эта ни эта не будет работать?'''

Обозначим пары <tex> <x,y></tex>, для которых такой <tex>z</tex> существует как какой нибудь язык <tex>L_1</tex>. <tex>L_1 = \forall{<x,y>|\varphiexists{}z}: |\varphi{}|=m \forallpsi{x_1}..\forall{x_m} если C_m(\varphi{}x,y,z)=0 \Rightarrow \varphi{(x_1)}=0 иначе C_{m-1}(\varphi|_{x_1=0})=0 \Rightarrow \varphi|_{x_1=0}(x_2)=0</tex>.

Заметим что <tex>C_{m-1}(L_1 \varphi{}|_{x_1=1})=0 \Rightarrow \varphi{}|_{x_1=0}(x_2)=0in NP</tex> по определению <tex>NP</tex>

Таким образом получается, что <tex>C_{m-1}(L=\varphi{}x|\forall{x_1=0y}) <x,y>\veein{L_1} C_{m-1}(\varphi{}|_{x_1=1})</tex> И рекурсивно вызываемся от того из них которое равно 1. Ту же самую формулу но записываем от того из них которое равно 1 (это же предикат но для того из них фи при х1= для которого труе)Второй вариант был угадать не только будевы схемы для сат но и те которые выдают нам правильные значения

кодирует <tex>i</tex> символов, разрешимых логической схемой <tex>C_i</tex>. Размер <tex>|C_i|\le p(n)</tex>.Это означает что для фиксированного <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>C_n</tex> решает <tex>SAT</tex> <tex> \exists{C_n} Leftrightarrow</tex> если <tex>\forall{\varphi{}} (\forall{x} \varphi{ (fi(x)}=0 1 \Leftrightarrow Rightarrow C_n(\varphi{}fi)=01)</tex>.

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

Рассмотрим Внутри будем проверять используемый набор <tex>L_1 \forall{\varphi{}} (C_{|\varphi{}|}(\varphi{})=0 \Rightarrow \forall{x} \varphi{}(x)= 0)\vee{}</tex> <x,ytex>(C_{|\existsvarphi{z}: |}(\psivarphi{(x,y,z})=1 \Rightarrow \varphi{}|_{x_1=0}\in SAT или \varphi{}|_{x_1=1} \in SAT)</tex>

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

Что означает <tex>C_n\forall{\varphi{}}: |\varphi{}|=m \forall{x_1}..\forall{x_m} </tex> решает <tex>SATC_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.