Теорема Карпа-Липтона

Формулировка

Теорема Карпа-Липтона

[math]NP \subset P/poly[/math] то [math]\Sigma_2=\Pi_2[/math]

Доказательство

Пусть есть логические схемы для [math]NP[/math] (для любой задачи из NP). Зафиксируем любую задачу из [math]NP[/math]. Например пусть [math]SAT[/math] разрешается логическими схемами [math] C_1...C_n... [/math] ([math]SAT[/math] с одним битом разрешается логической схемой [math]C_1[/math], [math]SAT[/math] с двумя переменными логической схемой [math]C_2[/math] и т.д.).

Что значит "разрешается логической схемой"?

Это значит что если на вход логической схеме подать каким-то логичным образом закодированную формулу, то на выходе получется логичным образом в виде 0 и 1 закодированный ответ - имеется разложение или нет. И причем размер этой логической схемы [math]|C_n|\le p(n) [/math], где [math]p(n)[/math] - какой-то полином.

Здесь не утверждается, что эти логические схемы можно как-то конструктивно построить. Если бы их было возможно построить за полином, то это бы означало, что [math]SAT_2=\Pi_2[/math] и значит [math]P = NP[/math].

Итак, получается, что если зафиксировать [math]n[/math], то для этого фиксированного [math]n[/math] будет

[math]\exists{C_n}\forall{} формулы \varphi{} (\varphi{} \in{} SAT  |\varphi{}|=n \Leftrightarrow C_n(\varphi{})=1)[/math] 
[math] \exists{C_n} \forall{\varphi{}} (\forall{x} \varphi{(x)}=0 \Leftrightarrow C_n(\varphi{})=0)[/math], где [math]x[/math] - вход длины [math]n[/math]

Рассмотрим язык [math]L\in \Pi_2[/math]. Это означает, что [math]x\in L \Leftrightarrow \forall{y} \exists{z}: \psi{(x,y,x)}[/math]

Что такое [math]\exists{z}:\psi{(x,y,z)}[/math]?

---

Обозначим пары [math]\lt x,y\gt [/math], для которых такой [math]z[/math] существует как какой нибудь язык [math]L_1[/math].

[math]L_1 = \{\lt x,y\gt |\exists{z}: \psi{(x,y,z)}\}[/math].

Заметим что [math]L_1 \in NP[/math] по определению [math]NP[/math]

Таким образом получается, что

[math]L=\{x|\forall{y} \lt x,y\gt \in{L_1}\}[/math]

---

Требуется доказать, что [math]L\in \Sigma_1[/math]

Если [math]L_1\in{} NP[/math] то [math]L_1 \le{}_m SAT[/math] с помощью [math]f[/math], т.е.

[math]L=\{x|\forall{y} f(\lt x,y\gt )\in{SAT}\}[/math]

Что такое "[math]f(\lt x,y\gt )\subset{SAT}[/math]"?

[math]f(\lt x,y\gt )\subset{SAT}[/math] [math]--[/math] для некоторого набора логических схем это означает выполнимость всего этого набора. Если предположить, что набор этих схем известен, то получится, что

[math]L=\{x|\forall{y} C_n(f(\lt x,y\gt ))=1\}[/math],

где [math]n[/math]- длина входа [math]\lt x,y\gt [/math].

Требуется откуда то взять этот набор. Его можно угадать, используя квантор "[math]\exists{}[/math]" снаружи.

[math]C_n[/math] существует по предположению, что [math]NP \subset{P/poly}[/math] т.е.

[math]L=\{x|\exists{C_n}: C_n[/math] решает [math]SAT[/math] и [math]\forall{y} C_n(f(\lt x,y\gt ))=1\}[/math]

Что такое Cn Решает SAT?

Запишем это используя квантор "[math]\forall{}[/math]".

[math]C_n[/math] решает [math]SAT[/math] [math]\Leftrightarrow[/math] если [math]\forall{\varphi} \forall{x}  (fi(x)=1 \Rightarrow C_n(fi)=1)[/math]

Воспользуемся самосведением [math]SAT[/math]:

[math]L=\{x|\exists{C1,C2,..,Cn} \forall{y} C_n(f(\lt x,y\gt ))=1\}[/math],

где - [math]C1,C2,..,Cn[/math] набор логических схем для [math]SAT[/math].

Внутри будем проверять используемый набор

[math]\forall{\varphi{}} (C_{|\varphi{}|}(\varphi{})=0 \Rightarrow \forall{x}  \varphi{}(x)=0) \label{f1}
\vee{}[/math]
   [math](C_{|\varphi{}|}(\varphi{})=1 \Rightarrow \varphi{}|_{x_1=0} \in SAT или \varphi{}|_{x_1=1} \in SAT)\label{f2}[/math]

Вот когда подставим x1=0 нужно будет использовать(получится более короткая формула) и используем для проверки логическую схему более короткую . Если она выдает 1 то мы опять подставляем либо 0 либо 1 и так далее. Это правильная проверка причем за полином

Если [math]C[/math] решает [math]SAT[/math] то все хорошо. Если нет, то зафиксируем формулу [math]\varphi{}_0[/math], которую он не решает. Если на этой формуле выдаст 0, а должна выдать 1, то получается что не удовлетворяет первую часть и не будет работать, если наоборот выдаст 1 а на самом деле формула не удавлетворима то обе скобки работать не будут.

Рассмотрим минимальную схему которая неправильна, тогда на той формуле, на которой эта схема неправильна. По предположению, что все более короткие формулы правильны,эта формула распознается схемами с меньшим числом входов. Поэтому эта и эта будут 0 и мы не узнаем набор схем. Можно попробовать развернуть формулу до конца. Видимо это будет выглядеть так

[math] \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[/math]

[math]C_{m-1}(\varphi{}|_{x_1=1})=0 \Rightarrow \varphi{}|_{x_1=0}(x_2)=0[/math]

[math]C_{m-1}(\varphi{}|{x_1=0}) \vee{} C_{m-1}(\varphi{}|_{x_1=1})[/math] И рекурсивно вызываемся от того из них которое равно 1. Ту же самую формулу но записываем от того из них которое равно 1 (это же предикат но для того из них фи при х1= для которого труе) Второй вариант был угадать не только будевы схемы для сат но и те которые выдают нам правильные значения

Получаем что [math]L\in \Sigma_2[/math] Теорема доказана