Изменения
Нет описания правки
Пусть <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>i</tex>, все пары <tex>\langle\phi, w_i\rangle \in LSAT</tex>. Тогда по сведению <tex>z_j \in S</tex> для всех <tex>j\ge i</tex>.
