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