211
правок
Изменения
м
\mathrm
{{Лемма
|about=1
|statement=<tex>LSAT \in \mathrm{NPC}</tex>.
|proof=
#Очевидно, что <tex>LSAT \in \mathrm{NP}</tex> (в качестве сертификата можно запросить <tex>x</tex>).
#Сведём <tex>SAT</tex> к <tex>LSAT</tex>. Для этого рассмотрим отображение <tex>\phi \mapsto \langle \phi, 1^{|\phi|}\rangle</tex>, где <tex>|\phi|</tex> — количество различных переменных в формуле <tex>\phi</tex>. Ясно, что данное преобразование можно сделать за полиномиальное время. Теперь докажем, что сведение верное.
#*Если <tex>\phi \in SAT</tex>, то формула <tex>\phi</tex> удовлетворима, а значит <tex>\exists x: x \le_{lex} 1^{|\phi|}, \phi(x)=1</tex>. Следовательно, <tex>\langle \phi, 1^{|\phi|}\rangle \in LSAT</tex>.
#*Если <tex>\langle \phi, 1^{|\phi|}\rangle \in LSAT</tex>, то <tex>\exists x: x \le_{lex} 1^{|\phi|}, \phi(x)=1</tex>. Значит формула <tex>\phi</tex> удовлетворима, и <tex>\phi \in SAT</tex>.
:Таким образом, <tex>SAT \le LSAT</tex>. Но <tex>SAT \in \mathrm{NPC}</tex>, а значит <tex>\forall L \in \mathrm{NP } \; L \le SAT</tex>. Тогда в силу транзитивности <tex>\forall L \in \mathrm{NP } \; L \le LSAT</tex>, то есть <tex>LSAT \in \mathrm{NPH}</tex>.Итого мы доказали, что <tex>LSAT \in \mathrm{NPH}</tex> и <tex>LSAT \in \mathrm{NP}</tex>. Тогда по определению <tex>LSAT \in \mathrm{NPC}</tex>.
}}
|author=Махэни
|statement=
<tex>\mathrm{NPC } \cap \mathrm{SPARSE } \ne \varnothing \Rightarrow P=NP</tex>.|proof=Пусть <tex>S \in \mathrm{NPC } \cap \mathrm{SPARSE}</tex>.
Так как <tex>S\in \mathrm{NPC}</tex>, и <tex>LSAT \in \mathrm{NP}</tex>, то существует полиномиальная функция сведения <tex>f</tex> такая, что <tex>\langle \phi, y \rangle \in LSAT \iff f(\langle \phi, y \rangle) \in S</tex>.
Так как функция <tex>f</tex> работает полиномиальное время, и <tex>|\phi|=|y|</tex> (<tex>|y|</tex> — длина вектора <tex>y</tex>), то <tex>f(\langle\phi,y\rangle) \le q(|\phi|)</tex>, где <tex>q</tex> — полином.
<tex>2^n(1-\frac1{r+1})^k \simeq 1</tex>. Отсюда <tex>k=O(rn)</tex> (это можно получить, выразив <tex>k</tex> через <tex>n</tex> и <tex>r</tex> и воспользовавшись [http://ru.wikipedia.org/wiki/Ряд_Тейлора#.D0.A0.D1.8F.D0.B4.D1.8B_.D0.9C.D0.B0.D0.BA.D0.BB.D0.BE.D1.80.D0.B5.D0.BD.D0.B0_.D0.BD.D0.B5.D0.BA.D0.BE.D1.82.D0.BE.D1.80.D1.8B.D1.85_.D1.84.D1.83.D0.BD.D0.BA.D1.86.D0.B8.D0.B9 формулой Тейлора] для логарифма).
Таким образом, мы можем разрешить язык <tex>LSAT</tex> за полиномиальное время, найдя лексиграфически минимальную строку, удовлетворяющую формулу, и сравнив её с нашим аргументом. Так как <tex>LSAT\in \mathrm{NPC}</tex>, то мы можем решить любую задачу из <tex>\mathrm{NP}</tex> за полиномиальное время, а значит <tex>\mathrm{P}=\mathrm{NP}</tex>.
}}
