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

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

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

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

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

Пусть есть логические схемы для [math]NP[/math] (любой задаче из NP).Например зафиксируем любую из NP например пусть сат разрешает логическими схемами [math]SAT : C_1...C_n...[/math], сат который поддерживается с одним битом разрешается логической схемой с1 сат с двумя переменными логической схемой с2...Что значит разрешается? Это значит что логическая схема, в инпуте которой который каким то логичным образом закодирована формула, а на выходе логичным образом в вмде 0 и один закодировано есть ли доказательство(разложение) или нет. И причем размер этой логической схемы не больше чем какой то полином от n. Но мы не утверждаем, что можем как то конструктивно их построить. Если бы мы могли за полином их построить, то это бы означало, что сат2=п2, что P=NP. Итак, что это означает, рассмотрим, это означает на самом деле что для любого n (зафиксируем n)

Это означает что для фиксированного [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} формулы длины n \varphi{(x)}=0 \Leftrightarrow C_n(\varphi{})=0)[/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] Теорема доказана