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

Материал из Викиконспекты
Перейти к: навигация, поиск
м
Строка 1: Строка 1:
 
{{Определение
 
{{Определение
 
|definition=
 
|definition=
<tex>LSAT=\{\langle\phi,y\rangle | \exists x: x<_{lex}y, \phi(x) = 1\}</tex>.
+
<tex>LSAT=\{\langle\phi,y\rangle | \exists x: x\le_{lex}y, \phi(x) = 1\}</tex>.
 
}}
 
}}
  
Строка 11: Строка 11:
 
#Сведём <tex>SAT</tex> к <tex>LSAT</tex>. Для этого рассмотрим отображение <tex>\phi \mapsto \langle \phi, 1^m\rangle</tex>, где <tex>m</tex> — количество различных аргументов в формуле <tex>\phi</tex>. Ясно, что данное преобразование можно сделать за полиномиальное время. Теперь докажем, что сведение верное.  
 
#Сведём <tex>SAT</tex> к <tex>LSAT</tex>. Для этого рассмотрим отображение <tex>\phi \mapsto \langle \phi, 1^m\rangle</tex>, где <tex>m</tex> — количество различных аргументов в формуле <tex>\phi</tex>. Ясно, что данное преобразование можно сделать за полиномиальное время. Теперь докажем, что сведение верное.  
 
#*Если <tex>\phi \in SAT</tex>, то формула <tex>\phi</tex> удовлетворима, а значит <tex>\exists x: x <_{lex} 1^m, \phi(x)=1</tex>. Следовательно, <tex>\langle \phi, 1^m\rangle \in LSAT</tex>.
 
#*Если <tex>\phi \in SAT</tex>, то формула <tex>\phi</tex> удовлетворима, а значит <tex>\exists x: x <_{lex} 1^m, \phi(x)=1</tex>. Следовательно, <tex>\langle \phi, 1^m\rangle \in LSAT</tex>.
#*Если <tex>\langle \phi, 1^m\rangle \in LSAT</tex>, то <tex>\exists x: x <_{lex} 1^m, \phi(x)=1</tex>. Значит формула <tex>\phi</tex> удовлетворима, и <tex>\phi \in SAT</tex>.
+
#*Если <tex>\langle \phi, 1^m\rangle \in LSAT</tex>, то <tex>\exists x: x \le_{lex} 1^m, \phi(x)=1</tex>. Значит формула <tex>\phi</tex> удовлетворима, и <tex>\phi \in SAT</tex>.
 
:Таким образом, <tex>SAT \le LSAT</tex>. Но <tex>SAT \in NPC</tex>, а значит <tex>\forall L \in NP \; L \le SAT</tex>. Тогда в силу транзитивности <tex>\forall L \in NP \; L \le LSAT</tex>, то есть <tex>LSAT \in NPH</tex>.
 
:Таким образом, <tex>SAT \le LSAT</tex>. Но <tex>SAT \in NPC</tex>, а значит <tex>\forall L \in NP \; L \le SAT</tex>. Тогда в силу транзитивности <tex>\forall L \in NP \; L \le LSAT</tex>, то есть <tex>LSAT \in NPH</tex>.
 
Итого мы доказали, что <tex>LSAT \in NPH</tex> и <tex>LSAT \in NP</tex>. Тогда по определению <tex>LSAT \in NPC</tex>.
 
Итого мы доказали, что <tex>LSAT \in NPH</tex> и <tex>LSAT \in NP</tex>. Тогда по определению <tex>LSAT \in NPC</tex>.
Строка 19: Строка 19:
 
|about=2
 
|about=2
 
|statement=<tex>\langle\phi,y\rangle \in LSAT, y<_{lex}z</tex>. Тогда <tex>\langle\phi,z\rangle \in LSAT</tex>.
 
|statement=<tex>\langle\phi,y\rangle \in LSAT, y<_{lex}z</tex>. Тогда <tex>\langle\phi,z\rangle \in LSAT</tex>.
|proof=<tex>\langle\phi,y\rangle \in LSAT</tex>. Тогда <tex>\exists x: x<_{lex}y, \phi(x) = 1</tex>. Так как <tex>y<_{lex}z</tex>, то <tex>\exists x: x<_{lex}z, \phi(x) = 1</tex>, следовательно <tex>\langle\phi,z\rangle \in LSAT</tex>.
+
|proof=<tex>\langle\phi,y\rangle \in LSAT</tex>. Тогда <tex>\exists x: x\le_{lex}y, \phi(x) = 1</tex>. Так как <tex>y<_{lex}z</tex>, то <tex>\exists x: x<_{lex}z, \phi(x) = 1</tex>, следовательно <tex>\langle\phi,z\rangle \in LSAT</tex>.
 
}}
 
}}
  

Версия 11:14, 16 апреля 2012

Определение:
[math]LSAT=\{\langle\phi,y\rangle | \exists x: x\le_{lex}y, \phi(x) = 1\}[/math].


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


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

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

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

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

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

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

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

Из леммы 2 мы знаем, что, начиная с некоторого [math]i[/math], все пары [math]\langle\phi, w_i\rangle \in LSAT[/math]. Тогда по сведению [math]z_j \in S[/math] для всех [math]j\ge i[/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]\frac 1{r+1}[/math] часть множества подстановок.
  2. [math]z_i \ne z_j \, \forall i \ne j[/math]. Как было показано выше, если [math]w_0[/math] или [math]w_1[/math] лежат в [math]S[/math], то все последующие [math]w_i[/math] тоже лежат в [math]S[/math], но тогда [math]S[/math] содержит не менее [math]r+1[/math] строку длины не более, чем [math]q(|\phi|)[/math], что противоречит условию [math]|\{x\in S\, |\, |x| \le q(|\phi|)\}| \le r(|\phi|)[/math]. Следовательно [math]x\notin[w_0,w_1][/math], то есть его можно убрать из рассмотрения.

В обоих случаях мы сузили область поиска как минимум на [math]\frac 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(1-\frac1{r+1})^k[/math] строк. Оценим [math]k[/math].

[math]2^n(1-\frac1{r+1})^k \simeq 1[/math]. Отсюда [math]k=O(rn)[/math]. Таким образом, мы можем разрешить язык [math]LSAT[/math] за полиномиальное время, найдя лексиграфически минимальную строку, удовлетворяющую формулу, и сравнив её с нашим аргументом. Так как [math]LSAT\in NPC[/math], то мы можем решить любую задачу из [math]NP[/math] за полиномиальное время, а значит [math]P=NP[/math].
[math]\triangleleft[/math]