211
правок
Изменения
Нет описания правки
|statement=<tex>LSAT \in NPC</tex>.
|proof=
#Очевидно, что <tex>LSAT \in 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>x</tex>, удовлетворяющей формулу <tex>\phi</tex>.
Пусть <tex>n=|\phi|, r=r(|\phi|)</tex>. Изначально область поиска для <tex>x</tex> это — все строки длины <tex>n</tex>. Опишем одну итерацию поиска.
Разобьём текущее множество строк на <tex>r+1</tex> подотрезок примерно равной длины. Обозначим концы полученных подотрезков <tex>w_0,...,w_{r+1}</tex>. Пусть теперь <tex>z_i=f(\langle\phi,w_i\rangle)</tex>.
Из леммы (2 ) мы знаем, что, начиная с некоторого <tex>il</tex>, все пары <tex>\langle\phi, w_iw_l\rangle \in LSAT</tex>. Тогда по сведению <tex>z_j \in S</tex> для всех <tex>j\ge il</tex>.
Рассмотрим два случая:
# <tex>\exists i \ne j \, z_i=z_j</tex>. Строки <tex>z_i</tex> и <tex>z_j</tex> либо обе лежат в <tex>S</tex>, либо обе не лежат в <tex>S</tex>. Тогда по вышеуказанной причине <tex>x\notin [(w_i, w_j]</tex>. Значит мы можем исключить этот отрезок полуинтервал из рассматриваемого множества. Таким образом, мы удаляем не менее <tex>\frac 1{r+1}</tex> часть множества подстановок.# <tex>z_i \ne z_j \, \forall i \ne j</tex>. Как было показано выше, если <tex>w_0z_0</tex> или <tex>w_1z_1</tex> лежат в <tex>S</tex>, то все последующие <tex>w_iz_i</tex> тоже лежат в <tex>S</tex>, но тогда <tex>S</tex> содержит <tex>r+1</tex> строку длины не более, чем <tex>q(|\phi|)</tex>, что противоречит условию <tex>|\{x\in S\, |\, |x| \le q(|\phi|)\}| \le r(|\phi|)</tex>. Следовательно, <tex>x\notin[w_0,w_1]</tex>, то есть его можно убрать из рассмотрения.
В обоих случаях мы сузили область поиска как минимум на <tex>\frac 1{r+1}</tex> её размера.
Оценим время работы нашего алгоритма. После <tex>k</tex> итераций у нас останется не более <tex>2^n(1-\frac1{r+1})^k</tex> строк. Оценим <tex>k</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 NPC</tex>, то мы можем решить любую задачу из <tex>NP</tex> за полиномиальное время, а значит <tex>P=NP</tex>.
}}
