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

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

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

Если [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]

Что такое [math]C_n[/math] Решает [math]SAT[/math]?

Запишем это используя квантор "[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)
\vee{}[/math]
   [math](C_{|\varphi{}|}(\varphi{})=1 \Rightarrow \varphi{}|_{x_1=0} \in SAT или \varphi{}|_{x_1=1} \in SAT)[/math]

Если [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} [/math][math] C_m(\varphi{})=0 \Rightarrow \varphi{(x_1)}=0[/math]
иначе [math] 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.

Второй вариант был угадать не только булевы схемы для сат но и те схемы, которые выдают правильные значения.

Получаем что [math]L\in \Sigma_2[/math]

Теорема доказана