Теорема Махэни — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
Строка 2: Строка 2:
 
{{Определение
 
{{Определение
 
|definition=
 
|definition=
<tex>\mathrm{LSAT} = \{\langle \phi, y \rangle \mid \exists x: x \leqslant_{lex} y, \phi(x) = 1\}</tex>, где <tex> \phi </tex> {{---}} булева формула, и  <tex> x \leqslant_{lex} y </tex> означает, что вектор <tex> x </tex> лексикографически меньше или равен вектору <tex> y </tex>.
+
<tex>\mathrm{LSAT} = \{\langle \phi, y \rangle \mid \exists x: x \leqslant_{lex} y, \phi(x) = 1\}</tex>, где <tex> \phi </tex> {{---}} булева формула из <tex>n</tex> переменных, <tex>x, y \in \{0,1\}^{n} </tex> и отношение <tex> \leqslant_{lex} </tex> задает лексикографический порядок.
 
}}
 
}}
  
Строка 13: Строка 13:
 
#*Если <tex>\phi \in \mathrm{SAT}</tex>, то формула <tex>\phi</tex> удовлетворима, а значит <tex>\exists x: x \leqslant_{lex} 1^{|\phi|}, \phi(x)=1</tex>. Следовательно, <tex>\langle \phi, 1^{|\phi|}\rangle \in \mathrm{LSAT}</tex>.
 
#*Если <tex>\phi \in \mathrm{SAT}</tex>, то формула <tex>\phi</tex> удовлетворима, а значит <tex>\exists x: x \leqslant_{lex} 1^{|\phi|}, \phi(x)=1</tex>. Следовательно, <tex>\langle \phi, 1^{|\phi|}\rangle \in \mathrm{LSAT}</tex>.
 
#*Если <tex>\langle \phi, 1^{|\phi|}\rangle \in \mathrm{LSAT}</tex>, то <tex>\exists x: x \leqslant_{lex} 1^{|\phi|}, \phi(x)=1</tex>. Значит формула <tex>\phi</tex> удовлетворима, и <tex>\phi \in \mathrm{SAT}</tex>.
 
#*Если <tex>\langle \phi, 1^{|\phi|}\rangle \in \mathrm{LSAT}</tex>, то <tex>\exists x: x \leqslant_{lex} 1^{|\phi|}, \phi(x)=1</tex>. Значит формула <tex>\phi</tex> удовлетворима, и <tex>\phi \in \mathrm{SAT}</tex>.
:Таким образом, <tex>\mathrm{SAT} \leqslant \mathrm{LSAT}</tex>. Но <tex>\mathrm{SAT} \in \mathrm{NPC}</tex>, а значит <tex>\forall L \in \mathrm{NP} \; L \leqslant \mathrm{SAT}</tex>. Тогда в силу транзитивности <tex>\forall L \in \mathrm{NP} \; L \leqslant \mathrm{LSAT}</tex>, то есть <tex>\mathrm{LSAT} \in \mathrm{NPH}</tex>.
+
:Таким образом, <tex>\mathrm{SAT} \leqslant \mathrm{LSAT}</tex>. Но [[Теорема Кука | <tex>\mathrm{SAT} \in \mathrm{NPC}</tex>]], а значит <tex>\forall L \in \mathrm{NP} \; L \leqslant \mathrm{SAT}</tex>. Тогда в силу транзитивности <tex>\forall L \in \mathrm{NP} \; L \leqslant \mathrm{LSAT}</tex>, то есть <tex>\mathrm{LSAT} \in \mathrm{NPH}</tex>.
 
Итого мы доказали, что <tex>\mathrm{LSAT} \in \mathrm{NPH}</tex> и <tex>\mathrm{LSAT} \in \mathrm{NP}</tex>. Тогда по определению <tex>\mathrm{LSAT} \in \mathrm{NPC}</tex>.
 
Итого мы доказали, что <tex>\mathrm{LSAT} \in \mathrm{NPH}</tex> и <tex>\mathrm{LSAT} \in \mathrm{NP}</tex>. Тогда по определению <tex>\mathrm{LSAT} \in \mathrm{NPC}</tex>.
 
}}
 
}}
Строка 27: Строка 27:
 
<tex>\mathrm{SPARSE}=\{L \mid \exists</tex> полином <tex> p: \forall n \, |L \cap \Sigma^n| \leqslant p(n)\}</tex>
 
<tex>\mathrm{SPARSE}=\{L \mid \exists</tex> полином <tex> p: \forall n \, |L \cap \Sigma^n| \leqslant p(n)\}</tex>
 
}}
 
}}
То есть множество языков, таких что множество слов длины <tex> n </tex> из языка ограничено полиномом от <tex> n </tex>.
+
То есть множество языков таких, что множество слов длины <tex> n </tex> из языка ограничено полиномом от <tex> n </tex>.
  
 
'''Пример:''' <tex> \{1^{n} \mid n</tex>-я машина Тьюринга останавливается на <tex> Y \} \in \mathrm{SPARSE}</tex>. Более того, любой унарный язык принадлежит <tex>\mathrm{SPARSE} </tex> (просто принять <tex> p(n) = 1 </tex>).
 
'''Пример:''' <tex> \{1^{n} \mid n</tex>-я машина Тьюринга останавливается на <tex> Y \} \in \mathrm{SPARSE}</tex>. Более того, любой унарный язык принадлежит <tex>\mathrm{SPARSE} </tex> (просто принять <tex> p(n) = 1 </tex>).

Версия 13:56, 27 марта 2016

Введём вспомогательный язык [math]\mathrm{LSAT}[/math].

Определение:
[math]\mathrm{LSAT} = \{\langle \phi, y \rangle \mid \exists x: x \leqslant_{lex} y, \phi(x) = 1\}[/math], где [math] \phi [/math] — булева формула из [math]n[/math] переменных, [math]x, y \in \{0,1\}^{n} [/math] и отношение [math] \leqslant_{lex} [/math] задает лексикографический порядок.


Лемма (1):
[math]\mathrm{LSAT} \in \mathrm{NPC}[/math].
Доказательство:
[math]\triangleright[/math]
  1. Очевидно, что [math]\mathrm{LSAT} \in \mathrm{NP}[/math] (в качестве сертификата можно запросить [math]x[/math]).
  2. Сведём [math]\mathrm{SAT}[/math] к [math]\mathrm{LSAT}[/math]. Для этого рассмотрим отображение [math]\phi \mapsto \langle \phi, 1^{|\phi|}\rangle[/math], где [math]|\phi|[/math] — количество различных переменных в формуле [math]\phi[/math]. Ясно, что данное преобразование можно сделать за полиномиальное время. Теперь докажем, что сведение верное.
    • Если [math]\phi \in \mathrm{SAT}[/math], то формула [math]\phi[/math] удовлетворима, а значит [math]\exists x: x \leqslant_{lex} 1^{|\phi|}, \phi(x)=1[/math]. Следовательно, [math]\langle \phi, 1^{|\phi|}\rangle \in \mathrm{LSAT}[/math].
    • Если [math]\langle \phi, 1^{|\phi|}\rangle \in \mathrm{LSAT}[/math], то [math]\exists x: x \leqslant_{lex} 1^{|\phi|}, \phi(x)=1[/math]. Значит формула [math]\phi[/math] удовлетворима, и [math]\phi \in \mathrm{SAT}[/math].
Таким образом, [math]\mathrm{SAT} \leqslant \mathrm{LSAT}[/math]. Но [math]\mathrm{SAT} \in \mathrm{NPC}[/math], а значит [math]\forall L \in \mathrm{NP} \; L \leqslant \mathrm{SAT}[/math]. Тогда в силу транзитивности [math]\forall L \in \mathrm{NP} \; L \leqslant \mathrm{LSAT}[/math], то есть [math]\mathrm{LSAT} \in \mathrm{NPH}[/math].
Итого мы доказали, что [math]\mathrm{LSAT} \in \mathrm{NPH}[/math] и [math]\mathrm{LSAT} \in \mathrm{NP}[/math]. Тогда по определению [math]\mathrm{LSAT} \in \mathrm{NPC}[/math].
[math]\triangleleft[/math]
Лемма (2):
[math]\langle\phi,y\rangle \in \mathrm{LSAT}, y\lt _{lex}z[/math]. Тогда [math]\langle\phi,z\rangle \in \mathrm{LSAT}[/math].
Доказательство:
[math]\triangleright[/math]
[math]\langle\phi,y\rangle \in \mathrm{LSAT}[/math]. Тогда [math]\exists x: x\leqslant_{lex}y, \phi(x) = 1[/math]. Так как [math]y\lt _{lex}z[/math], то [math]\exists x: x\lt _{lex}z, \phi(x) = 1[/math], следовательно [math]\langle\phi,z\rangle \in \mathrm{LSAT}[/math].
[math]\triangleleft[/math]


Определение:
[math]\mathrm{SPARSE}=\{L \mid \exists[/math] полином [math] p: \forall n \, |L \cap \Sigma^n| \leqslant p(n)\}[/math]

То есть множество языков таких, что множество слов длины [math] n [/math] из языка ограничено полиномом от [math] n [/math].

Пример: [math] \{1^{n} \mid n[/math]-я машина Тьюринга останавливается на [math] Y \} \in \mathrm{SPARSE}[/math]. Более того, любой унарный язык принадлежит [math]\mathrm{SPARSE} [/math] (просто принять [math] p(n) = 1 [/math]).

Теорема (Махэни):
[math]\mathrm{NPC} \cap \mathrm{SPARSE} \ne \varnothing \Rightarrow \mathrm{P}=\mathrm{NP}[/math].
Доказательство:
[math]\triangleright[/math]

Пусть [math]S \in \mathrm{NPC} \cap \mathrm{SPARSE}[/math].

Так как [math]S\in \mathrm{NPC}[/math] и [math]\mathrm{LSAT} \in \mathrm{NPC}[/math], то существует полиномиальная функция сведения [math]f[/math] такая, что [math]\langle \phi, y \rangle \in \mathrm{LSAT} \Leftrightarrow f(\langle \phi, y \rangle) \in S[/math].

Так как функция [math]f[/math] работает полиномиальное время, и [math]|\phi|\geqslant|y|[/math] ([math]|y|[/math] — длина вектора [math]y[/math]), то [math]f(\langle\phi,y\rangle) \leqslant q(|\phi|)[/math], где [math]q[/math] — полином. [math]S\in \mathrm{SPARSE}[/math], следовательно [math]\forall n \; |S \cap \Sigma^n|\leqslant p(n)[/math], где [math]p[/math] — некоторый полином.

Тогда [math]|\{x\in S \mid |x| \leqslant q(|\phi|)\}| \leqslant \displaystyle\sum\limits_{i=1}^{q(|\phi|)} p(i) = r(|\phi|)[/math], где [math]r[/math] — также полином.

Опишем алгоритм для нахождения лексикографически минимальной строки [math]x[/math], удовлетворяющей формуле [math]\phi[/math].

Пусть [math]n=|\phi|, r=r(|\phi|)[/math]. Изначально область поиска для [math]x[/math] — все строки длины [math]n[/math]. Опишем одну итерацию поиска.

Разобьём текущее множество строк на [math]r+1[/math] подотрезок примерно равной длины. Обозначим концы полученных подотрезков [math]w_0,...,w_{r+1}[/math]. Пусть теперь [math]z_i=f(\langle\phi,w_i\rangle)[/math].

Из леммы (2) мы знаем, что, начиная с некоторого [math]l[/math], все пары [math]\langle\phi, w_l\rangle \in \mathrm{LSAT}[/math]. Тогда по сведению [math]z_j \in S[/math] для всех [math]j\geqslant l[/math].

Рассмотрим два случая:

  1. [math]\exists i \ne j : z_i=z_j[/math]. Строки [math]z_i[/math] и [math]z_j[/math] либо обе лежат в [math]S[/math], либо обе не лежат в [math]S[/math]. Тогда по вышеуказанной причине [math]x\notin (w_i, w_j][/math]. Значит мы можем исключить этот полуинтервал из рассматриваемого множества. Таким образом, мы удаляем не менее [math]\dfrac 1{r+1}[/math] часть множества подстановок.
  2. [math]z_i \ne z_j \, \forall i \ne j[/math]. Как было показано выше, если [math]x \in [w_0, w_1][/math], то все [math]z_i[/math], начиная с [math]z_1[/math], лежат в [math]S[/math], но тогда [math]S[/math] содержит [math]r+1[/math] строку длины не более, чем [math]q(|\phi|)[/math], что противоречит условию [math]|\{x\in S \mid |x| \leqslant q(|\phi|)\}| \leqslant r(|\phi|)[/math]. Следовательно, [math]x\notin[w_0,w_1][/math], то есть его можно убрать из рассмотрения.

В обоих случаях мы сузили область поиска как минимум на [math]\dfrac 1{r+1}[/math] её размера.

Будем повторять эту процедуру до тех пор, пока не останется не более [math]r+1[/math] строки, которые мы можем проверить за полиномиальное время. Если какая-то из них удовлетворила формуле [math]\phi[/math], то [math]x=min(w_i), w_i[/math] удовлетворяет [math]\phi[/math]. Иначе, [math]x[/math] не существует.

Оценим время работы нашего алгоритма. После [math]k[/math] итераций у нас останется не более [math]2^n\left(1-\dfrac1{r+1}\right)^k[/math] строк. Оценим [math]k[/math].

[math]2^n\left(1-\dfrac1{r+1}\right)^k \simeq 1[/math]. Отсюда [math]k=O(rn)[/math] (это можно получить, выразив [math]k[/math] через [math]n[/math] и [math]r[/math] и воспользовавшись формулой Тейлора для логарифма).

Таким образом, мы можем разрешить язык [math]\mathrm{LSAT}[/math] за полиномиальное время, найдя лексикографически минимальную строку, удовлетворяющую формуле, и сравнив её с нашим аргументом. Так как [math]\mathrm{LSAT}\in \mathrm{NPC}[/math], то мы можем решить любую задачу из [math]\mathrm{NP}[/math] за полиномиальное время, а значит [math]\mathrm{P}=\mathrm{NP}[/math].
[math]\triangleleft[/math]

См. также

Источники информации