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

Лемма:

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