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

2012-06-07T19:31:05Z

178.178.20.180:

{{Лемма
|statement= Пусть <tex>\mathrm{SAT} \in \mathrm{P}/poly </tex>. Тогда существует такое семейство схем полиномиального размера, что для любой входной формулы <tex>\phi</tex> возвращается последовательность бит, удовлетворяющая <tex>\phi</tex>, если она существует, или же последовательность нулей в другом случае.
|proof=
Пусть нам дана формула <tex>\phi</tex> с <tex>n</tex> переменными. 
Попобуем построить схемы <tex>C_n^1, \ldots, C_n^n</tex>, работающие следующим образом:
*<tex>C_n^1(\phi) = 1 \Leftrightarrow \exists x_2,\ldots, x_n: \phi(1,x_2, \ldots, x_n)=1</tex>;
*<tex> \ldots </tex>
*<tex>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</tex>;
*<tex> \ldots </tex>
*<tex>C_n^n(\phi, b_1, \ldots, b_{n - 1}) = 1 \Leftrightarrow \phi(b_1, \ldots, b_{n-1}, 1)=1</tex>.
Задача определения возвращаемого значения таких схем тогда будет эквивалентна задаче <tex>\mathrm{SAT}</tex>. По условию <tex>\mathrm{SAT} \in \mathrm{P}/poly </tex>, следовательно, такие схемы существуют и каждая из них будет полиномиального размера. Рассмотрим последовательность: <tex>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})</tex>. Очевидно, что это будет последовательностью бит, которая удовлетворит <tex>\phi</tex>, или же последовательностью нулей, если <tex>\phi</tex> удовлетворить нельзя. Если при <tex>b_1=1</tex> формулу <tex>\phi</tex> удовлетворить возможно, то есть <tex>C_n^1(\phi)=1</tex>, то нужно взять <tex>b_1=1</tex>, если же нет, если <tex>C_n^1(\phi)=0</tex>, тогда имеет смысл искать следующие биты последовательности, удовлетворяющей <tex>\phi</tex> только при <tex>b_1=0</tex>. Следующие биты последовательности выбираются по аналогии. 
За <tex>C_n</tex> обозначим схему, строящую описанным алгоритмом требуемую последовательность. Очевидно, что она будет полиномиального размера (как совокупность <tex>n</tex> схем полиномиального размера). Это и есть требуемая схема для <tex>\phi</tex>.
}}

{{Теорема
|author=Карп, Липтон
|statement=
Если <tex>\mathrm{NP} \subset \mathrm{P}/poly</tex>, то <tex>\Sigma_2 = \Pi_2</tex>.
|proof=
Рассмотрим язык <tex>L \in \mathrm{\Pi_2}</tex>: <tex> \exists p \in poly, \phi \in \mathrm{\widetilde{P}}, \forall x \in L \Leftrightarrow \forall y \ \exists z : |y|,|z| \le p(|x|), \phi(x, y, z) = 1</tex>. 
Для фиксированного <tex>x</tex> <tex>\phi</tex> можно рассматривать как формулу с <tex>n</tex> битовыми переменными (так как мы знаем, что <tex>\phi \in \mathrm{\widetilde{P}}</tex>, а <tex>\mathrm{P} \subset \mathrm{P}/poly</tex>), где <tex>n</tex> {{---}} полином от длины входа <tex>x</tex> (из-за ограничений накладываемых по определению класса <tex>\mathrm{\Pi_2}</tex> на <tex>|y|, |z|)</tex>.
Для заданных <tex>x</tex> и <tex>y</tex> научимся находить такой <tex>z</tex>, что <tex>\phi(x,y,z)=1</tex>, если это возможно. Подставим значения <tex>x</tex> и <tex>y</tex> в формулу <tex>\phi</tex>. Теперь <tex>\phi</tex> зависит только от <tex>z</tex>: <tex>\phi_{xy}(z)</tex>.
Из предыдущей леммы мы установили существования семейство схем полиномиального размера <tex>C_1, \ldots, C_n, \ldots </tex> Запустим схему <tex>C_{p(|x|)}</tex> на <tex>\phi_{xy}</tex>. Эта схема вернет нам такое значение <tex>z</tex>, что <tex>\phi(x,y,z)=1</tex>, если <tex>\phi(x,y,z) </tex> удовлетворима для заданных <tex>x</tex> и <tex>y</tex>, или же последовательность нулей. 
Тогда определение языка <tex>L</tex> можно переписать: <tex>L = \{x \bigm| \forall y \ \phi(x, y, C_{p(|x|)}(\phi_{xy})) = 1\}</tex>. 
Рассмотрим язык <tex>L_1 = \{x\bigm|\exists G \ \forall y \ \phi(x, y, G(\phi_{xy})) = 1\}</tex>. 
Покажем, что <tex>L=L_1</tex>:
*<tex> L \subset L_1</tex> 
Очевидно. Можно за <tex>G</tex> взять <tex>C_{p(|x|)}</tex>.
*<tex>L_1 \subset L</tex>
Мы докажем это утверждение, если покажем, что если какое-то слово не принадлежит <tex>L</tex>, то оно не принадлежит и <tex>L_1</tex>. 
Если <tex>\exists y \ \forall z \ \phi(x,y,z)=0 </tex>, тогда <tex>\nexists G \ \forall y \ \phi(x, y, G(\phi_{xy}))=1</tex> 
Таким образом <tex>L =\{x\bigm|\exists G, |G| < p(|x|) \ \forall y, |y|<p(|x|) \ \phi(x, y, G(\phi_{xy})) = 1\}</tex>. Следовательно, <tex>L \in \Sigma_2</tex>.
}}

[[Категория: Теория сложности]]

Викиконспекты - Вклад участника [ru]

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