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

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

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

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

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

Пусть есть логические схемы для [math]NP[/math]. Например [math]SAT : C_1...C_n...[/math], который кодирует [math]i[/math] символов, разрешимых логической схемой [math]C_i[/math]. Размер [math]|C_i|\le p(n)[/math]. Это означает что для фиксированного [math]n[/math] [math]\exists{}[/math] такая логическая схема [math]C_n[/math], что [math]\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]L\in \Pi_2[/math]. Это означает, что [math]x\in L \Leftrightarrow \forall{y} \exists{z}: \psi{(x,y,x)}[/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 \Rightarrow 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 )\in{SAT}[/math] - это значит, что для некоторого набора формул выполняется для всего набора, если предположить, что [math]L=\{x|\forall{y} C_n(f(\lt x,y\gt ))=1\}[/math]

Но надо откуда-то взять этот набор. Можно его угадать, используя квантор существует. Добавим его. Так как [math]NP \subset P/poly[/math] то [math]L=\{x|\exists{C_n}: C_n решает SAT и \forall{y} C_n(f(\lt x,y\gt ))=1\}[/math]

Что означает [math]C_n[/math] решает [math]SAT[/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} - набор логических схем для SAT и\forall{y} C_n(f(\lt x,y\gt ))=1\}[/math]

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

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

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

[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]

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