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

Лемма:

Пусть [math]SAT \in P [/math], тогда для любой формулы [math]\phi \in SAT[/math] можно за полиномиальное время вывести набор значений, удовлетворяющий формуле.

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

[math]\triangleright[/math]

Если [math]\phi[/math] не содержит переменных, то есть является тождественной единицей, решение задачи тривиально. Иначе, выберем любую переменную [math]x[/math] из формулы [math]\phi[/math], и выполним подстановку [math]x = 0[/math]. Получим формулу [math]\phi_0[/math]. Если [math]\phi_0 \in SAT[/math] (по условию теоремы, проверку можно выполнить за полиномиальное время), то мы свели задачу к аналогичной с меньшим числом переменных. В противном случае, сведение выполняется подстановкой [math]x = 1[/math].

[math]\triangleleft[/math]

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

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

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

[math]\triangleright[/math]

Так как [math]NP \subset P/poly[/math], то для любого [math]n[/math] найдётся схема полиномиального размера [math] C_n[/math], такая что [math]C_{|x|}(x) = \left[x \in SAT\right][/math]. Тогда, найдётся и схема полиномиального размера [math] D_n[/math], выдающая для [math]x \in SAT[/math] набор значений, удовлетворяющий формуле. Рассмотрим язык [math]L \in \Pi_2[/math], [math]L = \{z:\forall x [/math] [math]\exists y [/math] [math] \phi(x, y, z)\}[/math]. Рассмотрим формулу [math]\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_{|z|}(x, z), z)\}[/math]. Покажем что [math]\forall x[/math] [math] \phi(x,D_{|z|}(x, z), z)[/math] [math]\Leftrightarrow[/math] [math]\exists D[/math] [math] \forall x[/math] [math]\phi(x, D(x, z), z)[/math]. Очевидно, из первого следует второе, так как [math]\exists D = D_{|z|}[/math]. Если первое ложно, то [math]\exists x[/math][math]\forall y[/math] [math]\phi(x, y, z) = 0[/math], а значит [math]\forall D \phi (x, D_{|z|}(x, z), z)[/math], то есть второе ложно. Итого, язык [math]L=\{z:\exists D[/math] [math]\forall x[/math] [math]\phi(x, D(x, z), z)\}[/math], значит [math]L \in \Sigma_2[/math].

[math]\triangleleft[/math]