Изменения

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

Пусть есть логические схемы для <tex>NP</tex> (для любой задачи из NP). Зафиксируем любую задачу из <tex>NP</tex>. Например пусть <tex>SAT</tex> разрешается логическими схемами <tex> C_1...C_n... </tex> (<tex>SAT который кодирует i символов, разрешимых </tex> с одним битом разрешается логической схемой C_i. Размер |C_i|<=p(n).Это означает что для фиксированного n найдется такая логическая схема C_n что для любого fi (fi \in tex>C_1</tex>, <tex>SAT & |fi|=n <=/tex> с двумя переменными логической схемой <tex> C_n(fi)=1)Существует C_n для любого fi (для любого x fi(x)=0 C_2<=/tex>C_n(fi)=0и т.д.).

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

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

для любого fi Если <tex>C</tex> решает <tex>SAT</tex> то все хорошо. Если нет, то зафиксируем формулу <tex>\varphi{}_0</tex>, которую он не решает. Если на этой формуле выдаст 0, а должна выдать 1, то получается что не удовлетворяет первую часть предыдущего выражения и, значит, не будет работать. Если наоборот выдаст 1 а на самом деле формула не удавлетворима то обе скобки не выполнятся и опять формула работать не будет. Рассмотрим минимальную неправильную схему. Тогда на той формуле, на которой эта схема неправильна, по предположению, что все более короткие формулы правильны,эта формула распознается схемами с меньшим числом входов. Поэтому обе скобки будут 0 и мы не узнаем набор схем. Развернем формулу до конца.  <tex> \forall{\varphi{}}: |fi\varphi{}|=m для любого \forall{x_1}...любого \forall{x_m если } </tex><tex> C_m(fi\varphi{})=0 => fi\Rightarrow \varphi{(x_1)}=0 </tex> иначе C_m<tex> C_{m-1}(fi\varphi|_x_1_{x_1=0})=0 => fi\Rightarrow \varphi|_x1_{x_1=0}(x2x_2)=0</tex>C_m <tex>C_{m-1}(fi\varphi{}|_x1_{x_1=1})=0 =>fi\Rightarrow \varphi{}|_x1_{x_1=0}(x2x_2)=0</tex>C_m <tex>C_{m-1}(fi\varphi{}|x1{x_1=0}) галочка C_m\vee{} C_{m-1}(fi\varphi{}|x1_{x_1=1})</tex> Далее рекурсивно записываем ту же самую формулу от того из них, которое равно 1. Второй вариант был угадать не только булевы схемы для сат но и те схемы, которые выдают правильные значения.