|
Пусть [math]S \in \mathrm{NPC} \cap \mathrm{SPARSE}[/math].
Так как [math]S\in \mathrm{NPC}[/math], и [math]\mathrm{LSAT} \in \mathrm{NP}[/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|=|y|[/math] ([math]|y|[/math] — длина вектора [math]y[/math]), то [math]f(\langle\phi,y\rangle) \le q(|\phi|)[/math], где [math]q[/math] — полином.
[math]S\in \mathrm{SPARSE}[/math], следовательно [math]\forall n \; |S \cap \Sigma^n|\le p(n)[/math], где [math]p[/math] — некоторый полином.
Тогда [math]|\{x\in S \bigm| |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|, 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\ge l[/math].
Рассмотрим два случая:
- [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] часть множества подстановок.
- [math]z_i \ne z_j \, \forall i \ne j[/math]. Как было показано выше, если [math]z_0[/math] или [math]z_1[/math] лежит в [math]S[/math], то все последующие [math]z_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]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]. |
