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

Материал из Викиконспекты
Перейти к: навигация, поиск
(Лемма)
Строка 1: Строка 1:
 
{{Лемма
 
{{Лемма
|statement= Пусть <tex>SAT \in P/poly </tex>, тогда существует семейство схем полиномиального размера <tex>D_n</tex>, таких, что для любой формулы <tex>\phi \in SAT</tex>, <tex>D_{|\phi|}(\phi)</tex> выводит набор значений, удовлетворяющих формуле.
+
|statement= Пусть <tex>SAT \in P/poly </tex>, тогда существует семейство схем полиномиального размера <tex>D_n</tex>, таких, что для любой формулы <tex>\phi \in SAT</tex>, <tex>D_{|\phi|}(\phi)</tex> выводит набор значений, удовлетворяющий формуле.
 
|proof=
 
|proof=
 
Если <tex>\phi</tex> не содержит переменных, то есть является тождественной единицей, решение задачи тривиально.
 
Если <tex>\phi</tex> не содержит переменных, то есть является тождественной единицей, решение задачи тривиально.
Иначе, выберем любую переменную <tex>x</tex> из формулы <tex>\phi</tex>, и выполним подстановку <tex>x = 0</tex>. Получим формулу <tex>\phi_0</tex>. Если <tex>\phi_0 \in SAT</tex> (так как по условию теоремы <tex>SAT \in P/poly</tex>, такую проверку можно сделать за полиномиальное время, вычислив соответствующую схему), то мы свели задачу к аналогичной с меньшим числом переменных. В противном случае, сведение выполняется подстановкой <tex>x = 1</tex>. Мы получили программу, работающую за полиномиальное время, а так как <tex>P \in P/poly</tex> то и семейство требуемых схем.
+
Иначе, выберем любую переменную <tex>x</tex> из формулы <tex>\phi</tex>, и выполним подстановку <tex>x = 0</tex>. Получим формулу <tex>\phi_0</tex>. Если <tex>\phi_0 \in SAT</tex> (так как по условию теоремы <tex>SAT \in P/poly</tex>, такую проверку можно сделать за полиномиальное время, вычислив соответствующую схему), то мы свели задачу к аналогичной с меньшим числом переменных. В противном случае, сведение выполняется подстановкой <tex>x = 1</tex>. Мы получили программу, работающую за полиномиальное время, а так как <tex>P \in P/poly</tex>, то и семейство требуемых схем.
 
}}
 
}}
  

Версия 20:12, 27 мая 2012

Лемма:
Пусть [math]SAT \in P/poly [/math], тогда существует семейство схем полиномиального размера [math]D_n[/math], таких, что для любой формулы [math]\phi \in SAT[/math], [math]D_{|\phi|}(\phi)[/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]SAT \in P/poly[/math], такую проверку можно сделать за полиномиальное время, вычислив соответствующую схему), то мы свели задачу к аналогичной с меньшим числом переменных. В противном случае, сведение выполняется подстановкой [math]x = 1[/math]. Мы получили программу, работающую за полиномиальное время, а так как [math]P \in P/poly[/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]\psi(x, z) = \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_{|\psi(x, z)|}(\psi(x, z)), z)\}[/math].
Покажем что [math](\forall x[/math] [math] \phi(x,D_{|\psi(x, z)|}(\psi(x, z)), z)[/math] [math])\Leftrightarrow[/math] [math](\exists G : [/math] [math] \forall x[/math] [math]\phi(x, G(\psi(x, z)), z))[/math].
Очевидно, из первого следует второе, так как [math]\exists G = D_{|\psi(x, z)|}[/math]. Если первое ложно, то [math]\exists x = x_0 : [/math] [math]\forall y[/math] [math]\phi(x, y, z) = 0[/math], а значит [math]\forall G [/math] [math]\exists x = x_0 : \phi (x, G(\psi(x, z)), z)[/math], то есть второе ложно.

Итого, язык [math]L=\{z:\exists G : [/math] [math]\forall x[/math] [math]\phi(x, G(\psi(x, z)), z)\}[/math], значит [math]L \in \Sigma_2[/math].
[math]\triangleleft[/math]