Материал из Викиконспекты
| Теорема (Карп — Липтон): |
Если [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] |
