Точные алгоритмы решения задачи о выполнимости формулы в КНФ общего вида: различия между версиями
Перейти к навигации
Перейти к поиску
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) |
||
| Строка 105: | Строка 105: | ||
'''''Граница для <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 + 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>''''' | ||
В настоящее время нетривиальная константная верхняя граница для a неизвестна. Однако, начиная с работы [ ], были предложены любопытные неконстнатнеы границы. Был разработан ряд рандомизированных и детерминированных алгоритмов, демонстрирующих последовательные улучшения. Лучшая на данный момент возможная граница достигается при помощи детерминированного алгоритма «разделяй и властвуй», применяющего следующую рекурсивную процедуру. Его заключается в дихотомии: либо каждый дизъюнкт входной формулы можно сократить до первых k литералов (тогда можно применить алгоритм k-КНФ), либо все эти литералы в одном из дизъюнктов можно считать ложными. Такой подход к сокращению дизъюнктов можно приписать Шулеру [ ], который использовал его в рандомизированной форме. Следующая версия детерминированного алгоритма, достигающего лучшей известной границы как для детерминированных, так и для рандомизированных алгоритмов, приведена в [5]). | В настоящее время нетривиальная константная верхняя граница для a неизвестна. Однако, начиная с работы [14], были предложены любопытные неконстнатнеы границы. Был разработан ряд рандомизированных и детерминированных алгоритмов, демонстрирующих последовательные улучшения. Лучшая на данный момент возможная граница достигается при помощи детерминированного алгоритма «разделяй и властвуй», применяющего следующую рекурсивную процедуру. Его заключается в дихотомии: либо каждый дизъюнкт входной формулы можно сократить до первых k литералов (тогда можно применить алгоритм k-КНФ), либо все эти литералы в одном из дизъюнктов можно считать ложными. Такой подход к сокращению дизъюнктов можно приписать Шулеру [15], который использовал его в рандомизированной форме. Следующая версия детерминированного алгоритма, достигающего лучшей известной границы как для детерминированных, так и для рандомизированных алгоритмов, приведена в [5]). | ||
'''Процедура S''' | == '''Процедура S''' == | ||
Дано: КНФ-формула F и положительное целое число k. | Дано: КНФ-формула F и положительное целое число k. | ||