211
правок
Изменения
м
Нет описания правки
|proof=Пусть <tex>S \in NPC \cap SPARSE</tex>.
Так как <tex>S\in NPC</tex>, и <tex>LSAT \in NP</tex>, то существует полиномиальная функция сведения <tex>f:LSAT \mapsto S</tex> такая, что <tex>\langle \phi, y \rangle \in NPC LSAT \iff f(\langle \phi, y \rangle) \in S</tex>.
Так как функция <tex>f</tex> работает полиномиальное время, и <tex>|\phi|=|y|</tex>, то <tex>f(\langle\phi,y\rangle) \le q(|\phi|)</tex>, где <tex>q</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+21}</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>.
