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

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

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

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

[math]\triangleright[/math]

Так как [math]NP \subset P/poly[/math], то [math]\forall n[/math] [math]\exists [/math] схема полиномиального размера [math] C_n[/math], такая что [math]C_{|x|}(x) = x \in SAT[/math]. Тогда [math]\forall n [/math] [math]\exists [/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_{|x|}(x, z), z)\}[/math]. Покажем что [math]\forall x[/math] [math] \phi(x,D_{|x|}(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]