211
правок
Изменения
м
Нет описания правки
Опишем алгоритм для нахождения лексиграфически минимальной строки <tex>x</tex>, удовлетворяющей формулу <tex>\phi</tex>.
Пусть <tex>n=|\phi|, r=r(|\phi|)</tex>. Разобьём множество бинарных строк длины <tex>n</tex> на <tex>r+1</tex> подотрезок так, чтобы каждый подотрезок содержал не более <tex>\frac{2^n}{r+1}</tex> строк. Обозначим концы полученных подотрезков <tex>w_0,...,w_{r+1}</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>.
