Теорема Карпа — Липтона — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
(Новая страница: «{{Теорема |author=Карп — Липтон |statement= Если <tex>NP \subset P/poly</tex>, то <tex>\Sigma_2 = \Pi_2</tex> |proof= Так как <tex>...»)
(нет различий)

Версия 20:51, 15 апреля 2012

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