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

Материал из Викиконспекты
Перейти к: навигация, поиск
м (rollbackEdits.php mass rollback)
 
(не показано 17 промежуточных версий 7 участников)
Строка 1: Строка 1:
 
{{Лемма
 
{{Лемма
|statement= Пусть <tex>SAT \in \mathrm{P}/poly </tex>, тогда для любой формулы <tex>\phi</tex> с <tex>n</tex> переменными, существует такая последовательность схем полиномиального размера <tex>C_n^1...C_n^n</tex>, что <tex>C_n^i</tex> возвращает значение <tex>i</tex>-й переменной в наборе переменных, удовлетворяющих <tex>\phi</tex>, если <tex>\phi \in SAT</tex>, или <tex>0</tex> если <tex>\phi \not \in SAT</tex>
+
|statement= Пусть <tex>\mathrm{SAT} \in \mathrm{P}/poly </tex>. Тогда существует такое семейство схем полиномиального размера, что для любой входной формулы <tex>\phi</tex> возвращается последовательность бит, удовлетворяющая <tex>\phi</tex>, если она существует, или же последовательность нулей в другом случае.
 
|proof=
 
|proof=
Зададимся формулой <tex>\phi</tex>. Определим семейство схем <tex>C_n^1 ... C_n^n</tex> так: схема <tex>C_n^i</tex> будет принимать на вход формулу <tex>\phi</tex> и <tex>i-1</tex> бит <tex>b_1 ... b_{i-1}</tex>, и возвращать <tex>1</tex> тогда и только тогда, когда существует набор переменных, удовлетворяющий <tex>\phi</tex>, такой что <tex>x_1 = b_1 ... x_{i-1}=b_{i-1}</tex> и <tex>x_i=1</tex>. Так как задача определения выходного значения таких схем принадлежит <tex>NP</tex>, то такие схемы существуют и имеют полиномиальный размер. Очевидно, что если формула <tex>\phi</tex> удовлетворима, то схема <tex>C_n^i</tex> вернет значение <tex>i</tex>-й переменной удовлетворяющего набора, в противном случае схема вернет <tex>0</tex>.  
+
Пусть нам дана формула <tex>\phi</tex> с <tex>n</tex> переменными.<br>
 +
Попробуем построить схемы <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>. Следующие биты последовательности выбираются по аналогии. <br>
 +
За <tex>C_n</tex> обозначим схему, строящую описанным алгоритмом требуемую последовательность. Очевидно, что она будет полиномиального размера (как совокупность <tex>n</tex> схем полиномиального размера). Это и есть требуемая схема для <tex>\phi</tex>.
 
}}
 
}}
  
Строка 11: Строка 19:
 
Если <tex>\mathrm{NP} \subset \mathrm{P}/poly</tex>, то <tex>\Sigma_2 = \Pi_2</tex>.
 
Если <tex>\mathrm{NP} \subset \mathrm{P}/poly</tex>, то <tex>\Sigma_2 = \Pi_2</tex>.
 
|proof=
 
|proof=
Рассмотрим язык <tex>L \in \Pi_2</tex>, <tex>L = \{x | \forall y_1 . \exists y_2 \phi(x, y_1, y_2)\}</tex>.<br/>
+
Рассмотрим язык <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>.<br>
Рассмотрим семейство схем <tex>С_n^1...C_n^n</tex>из леммы. <br> Используем выходы схем <tex>C_n^1...C_n^{i-1}</tex> как вход <tex>b_1...b_{i-1}</tex> схемы <tex>C_n^i</tex>, при этом заменяя те схемы <tex>C_n^i</tex>, которые возвращают значения переменных <tex>x</tex> и <tex>y_1</tex> на простые входы. Итого, получим схему <tex>C_n(\phi, x, y_1)</tex> и возвращающую такое значение <tex>y_2</tex>, что <tex> \phi(x, y_1, y_2) = 1</tex>, если <tex>\phi(x, y_1, y_2)</tex> удовлетворима для заданных <tex>x, y_1</tex>. <br> Теперь определение языка можно переписать так: <tex>L = \{x | \forall y_1 . \phi(x, y_1, C_n(\phi, x, y_1))\}</tex>. <br> Покажем что <tex>(\forall y_1 \phi(x, y_1, C_n(\phi, x, y_1)))</tex> <tex>\Leftrightarrow</tex> <tex>(\exists G \forall y_1 \phi(x, y_1, G(\phi, x, y_1)) )</tex>. <br> Очевидно, что из первого следует второе, т.к. <tex>\exists G = D_n</tex>. <br> Если первое ложно, то <tex>\exists y_1 = y_1^0 . \forall y_2 \phi(x, y_1^0, y_2) = 0</tex>, следовательно не существует такого <tex>G</tex>, что <tex>\forall y_1\phi(x, y_1, G(\phi, x, y_1)) )</tex>. <br>
+
Для фиксированного <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>L = \{x|\exists G \forall y_1 \phi(x, y_1, G(\phi, x, y_1))\}</tex>, значит <tex>L \in \Sigma_2</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>,  или же последовательность нулей. <br>
 +
Тогда определение языка <tex>L</tex> можно переписать: <tex>L = \{x \bigm| \forall y \ \phi(x, y, C_{p(|x|)}(\phi_{xy})) = 1\}</tex>.<br>
 +
Рассмотрим язык <tex>L_1 = \{x\bigm|\exists G \ \forall y \ \phi(x, y, G(\phi_{xy})) = 1\}</tex>. <br>
 +
Покажем, что <tex>L=L_1</tex>:
 +
*<tex> L \subset L_1</tex><br>
 +
Очевидно. Можно за <tex>G</tex> взять <tex>C_{p(|x|)}</tex>.
 +
*<tex>L_1 \subset L</tex>
 +
Мы докажем это утверждение, если покажем, что если какое-то слово не принадлежит <tex>L</tex>, то оно не принадлежит и <tex>L_1</tex>.<br>
 +
Если <tex>\exists y \ \forall z \ \phi(x,y,z)=0 </tex>, тогда <tex>\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(\phi_{xy})) = 1\}</tex>. Следовательно, <tex>L \in \Sigma_2</tex>. Значит, <tex>\mathrm{\Pi_2} \subset \mathrm{\Sigma_2} </tex>.<br>
 +
Докажем теперь, что <tex>\mathrm{\Sigma_2} \subset \mathrm{\Pi_2} </tex>.
 +
Рассмотрим язык <tex>L \in \mathrm{\Sigma_2}</tex>: <tex>L \in \mathrm{\Sigma_2} \Rightarrow \overline{L} \in \mathrm{\Pi_2} \Rightarrow \overline{L} \in \mathrm{\Sigma_2} \Rightarrow L \in \mathrm{\Pi_2}</tex>. Получается, что <tex>\mathrm{\Sigma_2} \subset \mathrm{\Pi_2} </tex>.
 +
Итого, <tex>\mathrm{\Sigma_2} = \mathrm{\Pi_2} </tex>.
 
}}
 
}}
  
 
[[Категория: Теория сложности]]
 
[[Категория: Теория сложности]]

Текущая версия на 19:27, 4 сентября 2022

Лемма:
Пусть [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]b_1=1[/math] формулу [math]\phi[/math] удовлетворить возможно, то есть [math]C_n^1(\phi)=1[/math], то нужно взять [math]b_1=1[/math], если же нет, если [math]C_n^1(\phi)=0[/math], тогда имеет смысл искать следующие биты последовательности, удовлетворяющей [math]\phi[/math] только при [math]b_1=0[/math]. Следующие биты последовательности выбираются по аналогии.

За [math]C_n[/math] обозначим схему, строящую описанным алгоритмом требуемую последовательность. Очевидно, что она будет полиномиального размера (как совокупность [math]n[/math] схем полиномиального размера). Это и есть требуемая схема для [math]\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] \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[/math].
Для фиксированного [math]x[/math] [math]\phi[/math] можно рассматривать как формулу с [math]n[/math] битовыми переменными (так как мы знаем, что [math]\phi \in \mathrm{\widetilde{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_{p(|x|)}[/math] на [math]\phi_{xy}[/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_{p(|x|)}(\phi_{xy})) = 1\}[/math].
Рассмотрим язык [math]L_1 = \{x\bigm|\exists G \ \forall y \ \phi(x, y, G(\phi_{xy})) = 1\}[/math].
Покажем, что [math]L=L_1[/math]:

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

Очевидно. Можно за [math]G[/math] взять [math]C_{p(|x|)}[/math].

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

Мы докажем это утверждение, если покажем, что если какое-то слово не принадлежит [math]L[/math], то оно не принадлежит и [math]L_1[/math].
Если [math]\exists y \ \forall z \ \phi(x,y,z)=0 [/math], тогда [math]\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})) = 1\}[/math]. Следовательно, [math]L \in \Sigma_2[/math]. Значит, [math]\mathrm{\Pi_2} \subset \mathrm{\Sigma_2} [/math].
Докажем теперь, что [math]\mathrm{\Sigma_2} \subset \mathrm{\Pi_2} [/math]. Рассмотрим язык [math]L \in \mathrm{\Sigma_2}[/math]: [math]L \in \mathrm{\Sigma_2} \Rightarrow \overline{L} \in \mathrm{\Pi_2} \Rightarrow \overline{L} \in \mathrm{\Sigma_2} \Rightarrow L \in \mathrm{\Pi_2}[/math]. Получается, что [math]\mathrm{\Sigma_2} \subset \mathrm{\Pi_2} [/math].

Итого, [math]\mathrm{\Sigma_2} = \mathrm{\Pi_2} [/math].
[math]\triangleleft[/math]