4430
правок
Irina (обсуждение | вклад) мНет описания правки |
Irina (обсуждение | вклад) |
||
Строка 9: | Строка 9: | ||
'''ResolveSat''' объединяет эти идеи и понятие разрешимости, значительно улучшая границы [9]. На данный момент алгоритму '''ResolveSat''' удается обеспечить наилучшие известные верхние границы для задачи выполнимости k-КНФ для всех <math>k \ge 5 \;</math>. Для k = 3 и k = 4 Ивама и Таками [6] получили наилучшую известную верхнюю границу при помощи рандомизированного алгоритма, сочетающего идеи алгоритма локального поиска Шонинга и '''ResolveSat'''. Более того, для задачи с предусловием о существовании единственного решения задачи выполнимости k-КНФ (далее «уникальная выполнимость»), считающейся одной из самых трудных вариаций задачи о выполнимости k-КНФ [2], '''ResolveSat''' достигает рекордных значений для всех <math>k \ge 3 \;</math>. Границы, полученные '''ResolveSat''' для задачи | '''ResolveSat''' объединяет эти идеи и понятие разрешимости, значительно улучшая границы [9]. На данный момент алгоритму '''ResolveSat''' удается обеспечить наилучшие известные верхние границы для задачи выполнимости k-КНФ для всех <math>k \ge 5 \;</math>. Для k = 3 и k = 4 Ивама и Таками [6] получили наилучшую известную верхнюю границу при помощи рандомизированного алгоритма, сочетающего идеи алгоритма локального поиска Шонинга и '''ResolveSat'''. Более того, для задачи с предусловием о существовании единственного решения задачи выполнимости k-КНФ (далее «уникальная выполнимость»), считающейся одной из самых трудных вариаций задачи о выполнимости k-КНФ [2], '''ResolveSat''' достигает рекордных значений для всех <math>k \ge 3 \;</math>. Границы, полученные '''ResolveSat''' для уникальной задачи и задачи общего вида для значений k = 3, 4, 5, 6, представлены в таблице 1. Эти границы сравниваются с границами алгоритма Шонинга [12], последовательно улучшенными результатами на базе локального поиска [1, 5, 11] и недавними изменениями, предложенными Ивамой и Таками [6]. Полученные для этих алгоритмов верхние границы выражаются в форме <math>2^{cn - o(n)} \;</math>, а значения в таблице отражают показатель c. Это сравнение охватывает только лучшие границы вне зависимости от типа алгоритма (рандомизированного или детерминированного). | ||
Строка 49: | Строка 49: | ||
|} | |} | ||
''В таблице представлен показатель c, используемый в значении границы <math>2^{cn - o(n)} \;</math> для уникального и общего случаев задачи k-КНФ, решаемой при помощи алгоритма ResolveSat, границы для k-КНФ | ''В таблице представлен показатель c, используемый в значении границы <math>2^{cn - o(n)} \;</math> для уникального и общего случаев задачи k-КНФ, решаемой при помощи алгоритма ResolveSat, границы алгоритма Шонинга для задачи k-КНФ [12], его улучшенной версии для 3-КНФ [1, 5, 11] и гибридной версии из работы [6]'' | ||
== Нотация == | == Нотация == |
правок