'''Теорема Карпа-Липтона'''
Если <math>NP \subset P/poly</math> то <math>\Sigma_2=\Pi_2</math>
== Доказательство ==
Рассмотрим язык <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,y>|\existsforall{zy}: \psi{(<x,y,z)>\in{L_1}\}</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}\Sigma_1}</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>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>f(<x,y>)\subset{SAT}</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 \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>NP</tex> входит в <tex>P/poly</tex> т.е.
<tex>L=\{x|\exists{C_n}: C_n решает SAT и \forall{y} C_n(f(<x,y>))=1\}</tex>
'''Что такое Cn <tex>C_n</tex> Решает <tex>SAT</tex>?'''
Запишем это используя квантор "<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>SAT</tex>: <tex>L=\{x|\exists{C1,C2,..,Cn} \forall{y} C_n(f(<x,y>))=1\}</tex>, где - решает <tex>C1,C2,..,CnSAT</tex> набор логических схем для <tex>SAT\Leftrightarrow</tex>.Внутри будем проверять используемый набор если <tex>\forall{\varphi{}} (C_{|\varphi{}|}(\varphi{})=0 \Rightarrow \forall{x} \varphi (fi(x)=0) (C_{|1 \varphi{}|}Rightarrow C_n(\varphi{}fi)=1 \Rightarrow \varphi{}|_{x_1=0} \in SAT или \varphi{}|_{x_1=1} \in SAT)</tex>
Воспользуемся самосведением <tex>SAT<// Если Cn(фи)tex>: <tex>L=0 то для любого \{x |\exists{C1,C2,..,Cn} \forall{y} C_n(для любого тут можем использовать) фиf(х<x,y>)=0Если Cn(фи)=1 то либо фи(ч1=0) принадлежит сат либо фи(х1=1) принадлежит сат тут не N а длина фи\}</tex>,Вот когда подставим x1=0 нужно будет использовать(получится более короткая формула) и используем где - <tex>C1,C2,..,Cn</tex> набор логических схем для проверки логическую схему более короткую . Если она выдает 1 то мы опять подставляем либо 0 либо 1 и так далее<tex>SAT</tex>. Это правильная проверка причем за полином
Если Внутри будем проверять используемый набор <tex>C\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> то все хорошо, если нет то зафиксируем формулу которую он не решает. Если выдаст 0 а должна выдать 1 то вот эту первую часть не удолветворяет и тут не будет работать, если наоборот выдаст 1 а на самом деле формула не удавлетворима то ни эта ни эта не будет работать
Рассмотрим минимальную схему которая неправильнаЕсли <tex>C</tex> решает <tex>SAT</tex> то все хорошо. Если нет, то зафиксируем формулу <tex>\varphi{}_0</tex>, тогда которую он не решает. Если на той этой формулевыдаст 0, на которой эта схема неправильна по предположению а должна выдать 1, то получается что все более короткие формулы правильныне удовлетворяет первую часть предыдущего выражения и,эта распознается схемами с меньшим числом входовзначит, поэтому и эта и эта будут 0 не будет работать. Если наоборот выдаст 1 а на самом деле формула не удавлетворима то обе скобки не выполнятся и мы опять формула работать не узнаем набор схем. Можно попробовать развернуть формулу до концабудет. Видимо это будет выглядеть так
<tex> \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)=0</tex>и мы не узнаем набор схем. Развернем формулу до конца.
<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.
<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>
Теорема доказана
