33
правки
Изменения
Нет описания правки
'''Теорема Карпа-Липтона'''
Если <math>NP \subset P/poly</math> то <math>\Sigma_2=\Pi_2</math>
== Доказательство ==
Пусть есть логические схемы для <tex>NP</tex> (для любой задачи из NP). Зафиксируем любую задачу из <tex>NP</tex>. Например пусть <tex>SAT</tex> разрешается логическими схемами <tex> C_1...C_n... </tex> (<tex>SAT</tex> с одним битом разрешается логической схемой <tex>C_1</tex>, <tex>SAT</tex> с двумя переменными логической схемой <tex>C_2</tex> и так далеет.д.).
Здесь не утверждается, что эти логические схемы можно как-то конструктивно построить. Если бы их было возможно построить за полином, то это бы означало, что <tex> \exists{C_n} \forall{\varphi{}} (\forall{x} формулы длины n \varphi{(x)}SAT_2=0 \Leftrightarrow C_n(\varphi{})Pi_2</tex> и значит <tex>P =0)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><x,y> \subset{L1}</tex>?Если <tex>L_1\in{} NP \Rightarrow тоL_1 \le{}_m SAT</tex> по карпу с помощью <tex>f</tex>, т.е. <tex>L=\{x|\forall{y} f(<x,y>)\insubset{SAT}\}</tex>"?'''
Требуется откуда то взять этот набор. Его можно угадать, используя квантор "<tex>\exists{}</tex>" снаружи.
<tex>C_n</tex> существует по предположению, что <tex>NP \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>
'''Что такое Cn Решает SAT? Запишем это используя квантор "<tex>\forall{}</tex>".<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>C_n</tex> решает <tex>SAT</ Если Cn(фи)=0 то для любого tex> <tex>\Leftrightarrow</tex> если <tex>\forall{\varphi} \forall{x } (для любого тут можем использовать) фиfi(х)=0Если Cn(фиx)=1 то либо фи\Rightarrow C_n(ч1=0fi) принадлежит сат либо фи(х1=1) принадлежит сат тут не N а длина фиВот когда подставим x1=0 нужно будет использовать(получится более короткая формула) и используем для проверки логическую схему более короткую . Если она выдает 1 то мы опять подставляем либо 0 либо 1 и так далее. Это правильная проверка причем за полином</tex>
Если <tex> \forall{\varphi{}}: |\varphi{}|=m \forall{x_1}.C</tex> решает <tex>SAT</tex> то все хорошо.\forall{x_m} если C_m(\varphi{})=0 \Rightarrow \varphi{(x_1)}=0 иначе C_{m-1}(\varphi|_{x_1=0})=0 \Rightarrow Если нет, то зафиксируем формулу <tex>\varphi|_{x_1=0}(x_2)=0_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. Ту записываем ту же самую формулу но записываем от того из них , которое равно 1 (это же предикат но для того из них фи при х1= для которого труе). Второй вариант был угадать не только будевы булевы схемы для сат но и те схемы, которые выдают нам правильные значения .
Получаем что <math>L\in \Sigma_2</math>
Теорема доказана