Изменения

Если <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>SATL\in \Pi_2</tex> . Это означает, что <tex>x\in L \Leftrightarrow</tex> если <tex>\forall{y} \varphiexists{z} : \forallpsi{(x} (fi(,y,x)=1 \Rightarrow C_n(fi)=1)}</tex>

'''Что такое <tex>\forall{\varphi{}} (C_{|\varphiexists{z}|}(\varphi{})=0 \Rightarrow :\forallpsi{x} \varphi(x,y,z)=0) (C_{|\varphi{}|}(\varphi{})=1 \Rightarrow \varphi{}|_{x_1=0} \in SAT или \varphi{}|_{x_1=1} \in SAT)</tex>// Если Cn(фи)=0 то для любого x (для любого тут можем использовать) фи(х)=0Если Cn(фи)=1 то либо фи(ч1=0) принадлежит сат либо фи(х1=1) принадлежит сат тут не N а длина фиВот когда подставим x1=0 нужно будет использовать(получится более короткая формула) и используем для проверки логическую схему более короткую . Если она выдает 1 то мы опять подставляем либо 0 либо 1 и так далее. Это правильная проверка причем за полином?'''

Рассмотрим минимальную схему которая неправильнаОбозначим пары <tex><x, тогда на той формулеy></tex>, на которой эта схема неправильна по предположению что все более короткие формулы правильныдля которых такой <tex>z</tex> существует как какой нибудь язык <tex>L_1</tex>. <tex>L_1 = \{<x,эта распознается схемами с меньшим числом входовy>|\exists{z}: \psi{(x, поэтому и эта и эта будут 0 и мы не узнаем набор схем. Можно попробовать развернуть формулу до концаy,z)}\}</tex>. Видимо это будет выглядеть так

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

Таким образом получается, что <tex>C_{m-1}(L=\varphi{}x|_\forall{x_1=1y})=0 \Rightarrow <x,y>\varphiin{L_1}|_{x_1=0\}(x_2)=0</tex>

<tex>C_{m-1}(\varphi{}|{x_1=0}) \vee{} C_{m-1}(\varphi{}|_{x_1=1})</tex>--

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

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

Рассмотрим язык Внутри будем проверять используемый набор <tex>L\in forall{\varphi{}} (C_{|\Pi_2</tex>. Это означает, что <tex>xvarphi{}|}(\in L varphi{})=0 \Leftrightarrow Rightarrow \forall{yx} \existsvarphi{z}: \psi{(x,y,x)=0)\vee{}</tex> Рассмотрим <tex>L_1 = \(C_{<x,y>|\existsvarphi{z}: |}(\psivarphi{(x,y,z})}\}</tex>  Но надо откуда-то взять этот набор. Можно его угадать, используя квантор существует. Добавим его.Так как <tex>NP =1 \subset P/poly</tex> то <tex>L=Rightarrow \varphi{x}|\exists_{C_nx_1=0}: C_n решает \in SAT и или \forallvarphi{y} C_n(f(<x,y>))|_{x_1=1} \}</tex> Что означает <tex>C_n</tex> решает <tex>in SAT)</tex>? Нужно переписать с квантором для любого.