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

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

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

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

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

Пусть есть логические схемы для [math]NP[/math]. Например [math]C_1...C_n...[/math] [math]SAT[/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]

Существует C_n для любого fi (для любого x fi(x)=0 <=>C_n(fi)=0).

Рассмотрим язык [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], т.е. L={x|для любого y f(<x,y>)\in{SAT}} f(<x,y>)\in SAT это значит, что для некоторого набора формул выполняется для всего набора, если предположить, что L={x|для любого y C_n(f(<x,y>))=1}

Но надо откуда-то взять этот набор. Можно его угадать, используя квантор существует. Добавим его. Так как NP \in P/poly L={x|существует C_n: C_n решает SAT и для любого y C_n(f(<x,y>))=1} Что означает C_n решает SAT? Нужно переписать с квантором для любого. C_n решает SAT <=> для любого \fi для любого x (если fi(x)=1 то C_n(fi)=1)

Воспользуемся самосведением SAT L={x|существуют C1C2...Cn - набор логических схем для SAT и для любого y C_n(f(<x,y>))=1} Внутри будем проверять используемый набор для любого fi (С_|fi|(fi)=0 => для любого x fi(x)=0) (C_|fi|(fi)=1 => fi|_x1=0 \in SAT или fi|_x1=1 \in SAT) Если C решает SAT то все хорошо, если нет то зафиксируем формулу на которой не решает. Если выдаст 0 а должна выдать 1 то первое не удолветворяет, если наоборот то обе не удовлетворяет.

для любого fi |fi|=m для любого x_1...любого x_m если C_m(fi)=0 => fi(x_1)=0 иначе C_m-1(fi|_x_1=0)=0 => fi|_x1=0(x2)=0 C_m-1(fi|_x1=1)=0 =>fi|_x1=0(x2)=0 C_m-1(fi|x1=0) галочка C_m-1(fi|x1=1)

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