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

Лемма:

Пусть [math]\mathrm{SAT} \in \mathrm{P}/poly [/math]. Тогда для любой формулы [math]\phi[/math] с [math]n[/math] переменными существует такая последовательность схем полиномиального размера [math]C_n^1, \ldots, C_n^n[/math], что [math]C_n^i[/math] возвращает значение [math]i[/math]-й переменной в наборе переменных, удовлетворяющих [math]\phi[/math], если [math]\phi \in \mathrm{SAT}[/math], или [math]0[/math] если [math]\phi \not \in \mathrm{SAT}[/math]

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

[math]\triangleright[/math]

Определим схемы следующим образом: [math]C_n^1(\phi) = 1 \Leftrightarrow \exists x_2,\ldots, x_n: \phi(1,x_2, \ldots, x_n)=1[/math]; [math] \ldots [/math] [math]C_n^i(\phi, b_1, \ldots, b_{i-1}) = 1 \Leftrightarrow \exists x_{i+1},\ldots, x_n: \phi(b_1, \ldots, b_{i-1},1,x_{i+1}, \ldots, x_n)=1[/math]; [math] \ldots [/math] [math]C_n^n(\phi, b_1, \ldots, b_{n - 1}) = 1 \Leftrightarrow \phi(b_1, \ldots, b_{n-1}, 1)=1[/math]. Задача определения возврщаемого значения таких схем — задача [math]\mathrm{SAT}[/math]. По условию [math]\mathrm{SAT} \in \mathrm{P}/poly [/math], следовательно, такие схемы существуют и каждая из них будет полиномиального размера. Рассмотрим последовательность: [math]b_1=C_n^1(\phi), b_2=C_n^2(\phi, b1), \ldots, b_n=C_n^n(\phi, b_1, \ldots, b_{n-1})[/math]. Очевидно, что это будет последовательностью бит, которая удовлетворяет [math]\phi[/math], или же последовательностью нулей, если [math]\phi[/math] удовлетворить нельзя.

[math]\triangleleft[/math]

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

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

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

[math]\triangleright[/math]

Рассмотрим язык [math]L \in \mathrm{\Pi_2}[/math], [math]L = \{x \bigm| \forall y_1 . \exists y_2 \phi(x, y_1, y_2)\}[/math]. Рассмотрим семейство схем [math]C_n^1, \ldots, C_n^n[/math] из леммы. Используем выходы схем [math]C_n^1, \ldots, C_n^{i-1}[/math] как вход [math]b_1, \ldots, b_{i-1}[/math] схемы [math]C_n^i[/math], при этом заменяя те схемы [math]C_n^i[/math], которые возвращают значения переменных [math]x[/math] и [math]y_1[/math] на простые входы. Итого, получим схему [math]C_n(\phi, x, y_1)[/math] и возвращающую такое значение [math]y_2[/math], что [math] \phi(x, y_1, y_2) = 1[/math], если [math]\phi(x, y_1, y_2)[/math] удовлетворима для заданных [math]x, y_1[/math]. Теперь определение языка можно переписать так: [math]L = \{x \bigm| \forall y_1 \phi(x, y_1, C_n(\phi, x, y_1))\}[/math]. Покажем что [math](\forall y_1 \phi(x, y_1, C_n(\phi, x, y_1)))[/math] [math]\Leftrightarrow[/math] [math](\exists G . \forall y_1 \phi(x, y_1, G(\phi, x, y_1)) )[/math]. Очевидно, что из первого следует второе, т.к. [math]\exists G = C_n[/math]. Если первое ложно, то [math]\exists y_1 = y_1^0 . \forall y_2 \phi(x, y_1^0, y_2) = 0[/math], следовательно не существует такого [math]G[/math], что [math]\forall y_1\phi(x, y_1, G(\phi, x, y_1)) )[/math]. Теперь определение исходного языка можно записать как [math]L = \{x \bigm| \exists G . \forall y_1 \phi(x, y_1, G(\phi, x, y_1))\}[/math], значит [math]L \in \Sigma_2[/math].

[math]\triangleleft[/math]