33
правки
Изменения
Нет описания правки
'''Теорема Карпа-Липтона'''
Если <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)
Это значит что если на вход логической схеме подать каким-то логичным образом закодированную формулу, то на выходе получется логичным образом в виде 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\existsin \Sigma_1</tex>''' Если <tex>L_1\in{C_n} NP</tex> то <tex>L_1 \forallle{}_m SAT</tex> с помощью <tex>f</tex>, т.е. <tex>L=\varphi{}} (x|\forall{xy} \varphi{f(<x,y>)\in{SAT}=0 \Leftrightarrow C_n(\varphi{})=0)</tex>.
<tex>L_1 f(<x,y>)\subset{SAT}</tex> <tex>--</tex> для некоторого набора логических схем это означает выполнимость всего этого набора. Если предположить, что набор этих схем известен, то получится, что <tex>L=\{x|\forall{y} C_n(f(<x,y>))=1\in NP}</tex> по определению ,где <tex>NPn</tex>- длина входа <tex><x,y></tex>.
Требуется откуда то взять этот набор. Его можно угадать, используя квантор "<tex>L={x|\forallexists{y} <x,y>\in{L_1}}</tex>" снаружи.
'''Что такое <tex>f(<x,y>)\in{SAT}C_n</tex> - это значит, что для некоторого набора формул выполняется для всего набора, если предположить, что Решает <tex>L=\{x|\forall{y} C_n(f(<x,y>))=1\}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>\forall{\varphi{}} (C_{|\varphi{}|}(\varphi{})=0 \Rightarrow \forall{x} \varphi{}(x)=0)
\vee{}</tex>
<tex>(C_{|\varphi{}|}(\varphi{})=1 \Rightarrow \varphi{}|_{x_1=0} \in SAT или \varphi{}|_{x_1=1} \in 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> \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>
Теорема доказана