Изменения

Пусть <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>.Пусть теперь <tex>z_i=f(\langle\phi,w_i\rangle)</tex>. Из леммы 2 мы знаем, что, начиная с некоторого <tex>i</tex>, все пары <tex>\langle\phi, w_i\rangle \in LSAT</tex>. Тогда по сведению <tex>z_j \in S</tex> для всех <tex>j\ge i</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_0</tex> или <tex>w_1</tex> лежат в <tex>S</tex>, то все последующие <tex>w_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>r</tex> строк, которые мы можем проверить за полиномиальное время. Если какая-то из них удовлетворила формулу <tex>\phi</tex>, то <tex>x=min(w_i), w_i</tex> удовлетворяет <tex>\phi</tex>. Иначе, <tex>x</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>LSAT</tex> за полиномиальное время, найдя лексиграфически минимальную строку, удовлетворяющую формулу, и сравнив её с нашим аргументом. Так как <tex>LSAT\in NPC</tex>, то мы можем решить любую задачу из <tex>NP</tex> за полиномиальное время, а значит <tex>P=NP</tex>.