211
правок
Изменения
м
Нет описания правки
Тогда <tex>|\{x\in S\, |\, |x| \le q(|\phi|)\}| \le \sum\limits_{i=1}^{q(|\phi|)} p(i) = r(|\phi|)</tex>, где <tex>r</tex> — также полином.
Опишем алгоритм для нахождения лексиграфически лексикографически минимальной строки <tex>x</tex>, удовлетворяющей формулу <tex>\phi</tex>.
Пусть <tex>n=|\phi|, r=r(|\phi|)</tex>. Изначально область поиска для <tex>x</tex> — все строки длины <tex>n</tex>. Опишем одну итерацию поиска.
