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

Лемма:

Пусть [math]SAT \in \mathrm{P}/poly [/math], тогда существует семейство схем полиномиального размера [math]D_n[/math] таких, что для любой формулы [math]\phi \in SAT[/math] c [math]n[/math] переменными, [math]D_{n}(\phi)[/math] выводит набор значений, удовлетворяющий формуле, или последовательность нулей если [math]\phi \not \in SAT[/math]

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

[math]\triangleright[/math]

Зададимся формулой [math]\phi[/math]. Определим семейство схем [math]C_n^1 ... C_n^n[/math] так: схема [math]C_n^i[/math] будет принимать на вход формулу [math]\phi[/math] и [math]i-1[/math] бит [math]b_1 ... b_{i-1}[/math], и возвращать [math]1[/math] тогда и только тогда, когда существует набор переменных, удовлетворяющий [math]\phi[/math], такой что [math]x_1 = b_1 ... x_{i-1}=b_{i-1}[/math] и [math]x_i=1[/math]. Так как задача определения выходного значения таких схем принадлежит [math]NP[/math], то такие схемы существуют и имеют полиномиальный размер. Очевидно, что если формула [math]\phi[/math] удовлетворима, то схема [math]C_n^i[/math] вернет значение [math]i[/math]-й переменной удовлетворяющего набора, в противном случае схема вернет [math]0[/math]. Теперь используем выходы схем [math]C_n^1...C_n^{i-1}[/math] как вход [math]b_1...b_{i-1}[/math] схемы [math]C_n^i[/math] и получим схему с [math]n[/math] выходами, возвращающую требуемые набор.

[math]\triangleleft[/math]

Теорема (Карп, Липтон):

Если [math]\mathrm{NP} \subset \mathrm{P}/poly[/math], то [math]\Sigma_2 = \Pi_2[/math].

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

[math]\triangleright[/math]

Так как [math]\mathrm{NP} \subset \mathrm{P}/poly[/math], то [math]SAT \in \mathrm{P}/poly[/math]. Тогда по лемме найдётся семейство схем полиномиального размера [math] D_n[/math] таких, что для любой формулы [math]\phi \in SAT[/math], [math]D_{|\phi|}(\phi)[/math] выводит набор значений, удовлетворяющий [math]\phi[/math]. Рассмотрим язык [math]L \in \Pi_2[/math], [math]L = \{z | \forall x [/math] [math]\exists y [/math] [math] \phi(x, y, z)\}[/math]. Рассмотрим формулу [math]\psi(x, z) = \exists y[/math] [math]\phi(x, y, z)[/math] как экземпляр задачи [math]SAT[/math]. Тогда определение языка [math]L[/math] можно переписать так: [math]L=\{z | \forall x[/math] [math] \phi(x,D_{|\psi(x, z)|}(\psi(x, z)), z)\}[/math]. Покажем что [math](\forall x[/math] [math] \phi(x,D_{|\psi(x, z)|}(\psi(x, z)), z)[/math] [math])\Leftrightarrow[/math] [math](\exists G : [/math] [math] \forall x[/math] [math]\phi(x, G(\psi(x, z)), z))[/math]. Очевидно, из первого следует второе, так как [math]\exists G = D_{|\psi(x, z)|}[/math]. Если первое ложно, то [math]\exists x = x_0 : [/math] [math]\forall y[/math] [math]\phi(x, y, z) = 0[/math], а значит [math]\forall G [/math] [math]\exists x = x_0 : \phi (x, G(\psi(x, z)), z)[/math], то есть второе ложно. Итого, язык [math]L=\{z | \exists G : [/math] [math]\forall x[/math] [math]\phi(x, G(\psi(x, z)), z)\}[/math], значит [math]L \in \Sigma_2[/math].

[math]\triangleleft[/math]