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

Материал из Викиконспекты
Перейти к: навигация, поиск
м
Строка 31: Строка 31:
 
Так как функция <tex>f</tex> работает полиномиальное время, и <tex>|\phi|=|y|</tex>, то <tex>f(\langle\phi,y\rangle) \le q(|\phi|)</tex>, где <tex>q</tex> — полином.
 
Так как функция <tex>f</tex> работает полиномиальное время, и <tex>|\phi|=|y|</tex>, то <tex>f(\langle\phi,y\rangle) \le q(|\phi|)</tex>, где <tex>q</tex> — полином.
 
<tex>S\in SPARSE</tex>. Следовательно <tex>\forall n |S \cap \Sigma^n|\le p(n)</tex>, где <tex>p</tex> — некоторый полином. Тогда <tex>|\{x\in S\, |\, |x| \le q(|\phi|)\}| \le \sum\limits_{i=1}^{q(|\phi|)} p(i) = r(|\phi|)</tex>, где <tex>r</tex> — также полином.
 
<tex>S\in SPARSE</tex>. Следовательно <tex>\forall n |S \cap \Sigma^n|\le p(n)</tex>, где <tex>p</tex> — некоторый полином. Тогда <tex>|\{x\in S\, |\, |x| \le q(|\phi|)\}| \le \sum\limits_{i=1}^{q(|\phi|)} p(i) = r(|\phi|)</tex>, где <tex>r</tex> — также полином.
 +
 +
Опишем алгоритм для нахождения лексиграфически минимальной строки <tex>x</tex>, удовлетворяющей формулу <tex>\phi</tex>.
 +
 +
Пусть <tex>n=|\phi|</tex>.  Разобьём множество бинарных строк длины <tex>n</tex> на <tex>r+1</tex> подотрезок так, чтобы каждый подотрезок содержал не больше <tex>\frac{2^n}{r+1}</tex> строк. Обозначим концы полученных подотрезков <tex>w_0,...,w_{r+2}</tex>.
 
}}
 
}}

Версия 01:43, 11 апреля 2012

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


Лемма:
[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 \lt _{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]
Лемма:
[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\lt _{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 NPC \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+2}[/math].
[math]\triangleleft[/math]