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

Материал из Викиконспекты
Перейти к: навигация, поиск
Строка 23: Строка 23:
 
Из предыдущей леммы мы получили семейство схем полиномиального размера <tex>C_1, \ldots, C_n, \ldots </tex> Запустим схему <tex>C_m</tex> на <tex>\phi_{xy}</tex>, где <tex>m=n-|x|-|y|</tex>. Эта схема вернет нам такое значение <tex>z</tex>, что <tex>\phi(x,y,z)=1</tex>, если <tex>\phi(x,y,z)</tex> удовлетворима для заданных <tex>x</tex> и <tex>y</tex>,  или же последовательность нулей. <br>
 
Из предыдущей леммы мы получили семейство схем полиномиального размера <tex>C_1, \ldots, C_n, \ldots </tex> Запустим схему <tex>C_m</tex> на <tex>\phi_{xy}</tex>, где <tex>m=n-|x|-|y|</tex>. Эта схема вернет нам такое значение <tex>z</tex>, что <tex>\phi(x,y,z)=1</tex>, если <tex>\phi(x,y,z)</tex> удовлетворима для заданных <tex>x</tex> и <tex>y</tex>,  или же последовательность нулей. <br>
 
Тогда определение языка <tex>L</tex> можно переписать: <tex>L = \{x \bigm| \forall y \ \phi(x, y, C_m(\phi_{xy}))\}</tex>.<br>
 
Тогда определение языка <tex>L</tex> можно переписать: <tex>L = \{x \bigm| \forall y \ \phi(x, y, C_m(\phi_{xy}))\}</tex>.<br>
Рассмотрим язык <tex>L_1 = \{x\bigm|\exists G \ \forall y \ \phi(x, y, G(x, y , \phi_{xy}))\}</tex>. <br>
+
Рассмотрим язык <tex>L_1 = \{x\bigm|\exists G \ \forall y \ \phi(x, y, G(\phi_{xy}))\}</tex>. <br>
 
Покажем, что <tex>L=L_1</tex>:
 
Покажем, что <tex>L=L_1</tex>:
 
*<tex> L \subset L_1</tex><br>
 
*<tex> L \subset L_1</tex><br>
Строка 30: Строка 30:
 
Мы докажем это утверждение, если покажем, что если какое-то слово не принадлежит <tex>L</tex>, то оно не принадлежит и <tex>L_1</tex>.<br>
 
Мы докажем это утверждение, если покажем, что если какое-то слово не принадлежит <tex>L</tex>, то оно не принадлежит и <tex>L_1</tex>.<br>
 
Пусть <tex>\exists y \ \forall z \ \phi(x,y,z)=0 \Rightarrow \nexists G \ \forall y \ \phi(x, y, G(\phi_{xy}))=1</tex> {{---}} очевидно.<br>
 
Пусть <tex>\exists y \ \forall z \ \phi(x,y,z)=0 \Rightarrow \nexists G \ \forall y \ \phi(x, y, G(\phi_{xy}))=1</tex> {{---}} очевидно.<br>
Таким образом <tex>L =\{x\bigm|\exists G, |G| < p(|x|) \ \forall y, |y|<p(|x|) \ \phi(x, y, G(x, y , \phi_{xy}))\}</tex>. Следовательно, <tex>L \in \Sigma_2</tex>.
+
Таким образом <tex>L =\{x\bigm|\exists G, |G| < p(|x|) \ \forall y, |y|<p(|x|) \ \phi(x, y, G(\phi_{xy}))\}</tex>. Следовательно, <tex>L \in \Sigma_2</tex>.
 
}}
 
}}
  
 
[[Категория: Теория сложности]]
 
[[Категория: Теория сложности]]

Версия 02:41, 7 июня 2012

Лемма:
Пусть [math]\mathrm{SAT} \in \mathrm{P}/poly [/math]. Тогда существует такое семейство схем полиномиального размера, что для любой входной функции [math]\phi[/math] возвращается последовательность бит, удовлетворяющая [math]\phi[/math], если она существует, или же последовательность нулей в другом случае.
Доказательство:
[math]\triangleright[/math]

Пусть нам дана функция [math]\phi[/math] с [math]n[/math] переменными.
Определим схемы [math]C_n^1, \ldots, C_n^n[/math] следующим образом:

  • [math]C_n^1(\phi) = 1 \Leftrightarrow \exists x_2,\ldots, x_n: \phi(1,x_2, \ldots, x_n)=1[/math];
  • [math] \ldots [/math]
  • [math]C_n^i(\phi, b_1, \ldots, b_{i-1}) = 1 \Leftrightarrow \exists x_{i+1},\ldots, x_n: \phi(b_1, \ldots, b_{i-1},1,x_{i+1}, \ldots, x_n)=1[/math];
  • [math] \ldots [/math]
  • [math]C_n^n(\phi, b_1, \ldots, b_{n - 1}) = 1 \Leftrightarrow \phi(b_1, \ldots, b_{n-1}, 1)=1[/math].
Задача определения возврщаемого значения таких схем — задача [math]\mathrm{SAT}[/math]. По условию [math]\mathrm{SAT} \in \mathrm{P}/poly [/math], следовательно, такие схемы существуют и каждая из них будет полиномиального размера. Рассмотрим последовательность: [math]b_1=C_n^1(\phi), b_2=C_n^2(\phi, b1), \ldots, b_n=C_n^n(\phi, b_1, \ldots, b_{n-1})[/math]. Очевидно, что это будет последовательностью бит, которая удовлетворит [math]\phi[/math], или же последовательностью нулей, если [math]\phi[/math] удовлетворить нельзя, ее и нужно вернуть. В итоге мы получили схему полиномиального размера [math]C_n(\phi)[/math].
[math]\triangleleft[/math]


Теорема (Карп, Липтон):
Если [math]\mathrm{NP} \subset \mathrm{P}/poly[/math], то [math]\Sigma_2 = \Pi_2[/math].
Доказательство:
[math]\triangleright[/math]

Рассмотрим язык [math]L \in \mathrm{\Pi_2}[/math], [math]L = \{x \bigm| \forall y \ \exists z \ \phi(x, y, z)\}[/math].
[math]\phi[/math] можно рассмтривать как функцию с [math]n[/math] битовыми переменныии (так как мы знаем, что [math]\phi \in \mathrm{P}[/math], а [math]\mathrm{P} \subset \mathrm{P}/poly[/math]), где [math]n[/math] — полином от длины входа [math]x[/math] (из-за ограничений накладываемых по определению класса [math]\mathrm{\Pi_2}[/math] на [math]|y|, |z|)[/math]. Для заданных [math]x[/math] и [math]y[/math] научимся находить такой [math]z[/math], что [math]\phi(x,y,z)=1[/math], если это возможно. Подставим значения [math]x[/math] и [math]y[/math] в функцию [math]\phi[/math]. Теперь [math]\phi[/math] зависит только от [math]z[/math]: [math]\phi_{xy}(z)[/math]. Из предыдущей леммы мы получили семейство схем полиномиального размера [math]C_1, \ldots, C_n, \ldots [/math] Запустим схему [math]C_m[/math] на [math]\phi_{xy}[/math], где [math]m=n-|x|-|y|[/math]. Эта схема вернет нам такое значение [math]z[/math], что [math]\phi(x,y,z)=1[/math], если [math]\phi(x,y,z)[/math] удовлетворима для заданных [math]x[/math] и [math]y[/math], или же последовательность нулей.
Тогда определение языка [math]L[/math] можно переписать: [math]L = \{x \bigm| \forall y \ \phi(x, y, C_m(\phi_{xy}))\}[/math].
Рассмотрим язык [math]L_1 = \{x\bigm|\exists G \ \forall y \ \phi(x, y, G(\phi_{xy}))\}[/math].
Покажем, что [math]L=L_1[/math]:

  • [math] L \subset L_1[/math]

Очевидно. Можно за [math]G[/math] взять [math]C_m[/math].

  • [math]L_1 \subset L[/math]

Мы докажем это утверждение, если покажем, что если какое-то слово не принадлежит [math]L[/math], то оно не принадлежит и [math]L_1[/math].
Пусть [math]\exists y \ \forall z \ \phi(x,y,z)=0 \Rightarrow \nexists G \ \forall y \ \phi(x, y, G(\phi_{xy}))=1[/math] — очевидно.

Таким образом [math]L =\{x\bigm|\exists G, |G| \lt p(|x|) \ \forall y, |y|\lt p(|x|) \ \phi(x, y, G(\phi_{xy}))\}[/math]. Следовательно, [math]L \in \Sigma_2[/math].
[math]\triangleleft[/math]