4446
правок
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) |
||
Строка 107: | Строка 107: | ||
'''''Граница для <math>\gamma</math>''''' | '''''Граница для <math>\gamma</math>''''' | ||
Для получения границы <math>|F|^{O(1)} \cdot 2^{0,10299l}</math> достаточно использовать пару <math>F[\neg a], F[I(a, F)]</math> подзадач (см. лемму 2(2)), обеспечивающую необходимое рекуррентное неравенство <math>t_l \le t_{l - 5} + t_{l | Для получения границы <math>|F|^{O(1)} \cdot 2^{0,10299l}</math> достаточно использовать пару <math>F[\neg a], F[I(a, F)]</math> подзадач (см. лемму 2(2)), обеспечивающую необходимое рекуррентное неравенство <math>t_l \le t_{l - 5} + t_{l - 17}</math>, и перейти к алгоритму с временем выполнения <math>|F|^{O(1)} \cdot 2^{0,30897m}</math>, если таковой пары нет. Недавнее и намного более технически сложное улучшение этого алгоритма [16] обеспечивает границу <math>|F|^{O(1)} \cdot 2^{0,0926l}.</math> | ||
'''''Граница для <math>\alpha</math>''''' | '''''Граница для <math>\alpha</math>''''' | ||
В настоящее время нетривиальная константная верхняя граница для | В настоящее время нетривиальная константная верхняя граница для <math>\alpha</math> неизвестна. Однако, начиная с работы [14], были предложены любопытные неконстантные границы. Был разработан ряд рандомизированных и детерминированных алгоритмов, демонстрирующих последовательные улучшения. Лучшая на данный момент возможная граница достигается при помощи детерминированного алгоритма «разделяй и властвуй», применяющего следующую рекурсивную процедуру. Его идея заключается в дихотомии: либо каждый дизъюнкт входной формулы можно сократить до первых k литералов (тогда можно применить алгоритм k-КНФ), либо все эти литералы в одном из дизъюнктов можно считать ложными. Такой подход к сокращению дизъюнктов можно приписать Шулеру [15], который использовал его в рандомизированной форме. Следующая версия детерминированного алгоритма, достигающего лучшей известной границы как для детерминированных, так и для рандомизированных алгоритмов, приведена в [5]). | ||
правок