K-КНФ-алгоритмы на основе поиска с возвратом: различия между версиями
Перейти к навигации
Перейти к поиску
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) |
||
| Строка 111: | Строка 111: | ||
Разрыв между границами для общего случая и для случая уникальной выполнимости при <math>k \in \{ 3, 4 \}</math> связан со слабостью анализа; было высказано предположение, что асимптотические границы для случая уникальной выполнимости выполняются в общем случае для всех k. Если это предположение верно, из него следует, что '''ResolveSat''' оказывается быстрее любого существующего алгоритма и в случае k = 3. | Разрыв между границами для общего случая и для случая уникальной выполнимости при <math>k \in \{ 3, 4 \}</math> связан со слабостью анализа; было высказано предположение, что асимптотические границы для случая уникальной выполнимости выполняются в общем случае для всех k. Если это предположение верно, из него следует, что '''ResolveSat''' оказывается быстрее любого существующего алгоритма и в случае k = 3. | ||
Таблица 1 | |||
{| class="wikitable" | {| class="wikitable" | ||
| Строка 147: | Строка 149: | ||
| | | | ||
|} | |} | ||
''В таблице представлен показатель c, используемый в значении границы <math>2^{cn - o(n)} \;</math> для уникального и общего случаев задачи k-КНФ, решаемой при помощи алгоритма ResolveSat, границы для k-КНФ и алгоритма Шонинга [12], его улучшенной версии для 3-КНФ [1, 5, 11] и гибридной версии из работы [6]'' | ''В таблице представлен показатель c, используемый в значении границы <math>2^{cn - o(n)} \;</math> для уникального и общего случаев задачи k-КНФ, решаемой при помощи алгоритма ResolveSat, границы для k-КНФ и алгоритма Шонинга [12], его улучшенной версии для 3-КНФ [1, 5, 11] и гибридной версии из работы [6]'' | ||