K-КНФ-алгоритмы на основе поиска с возвратом: различия между версиями

Разрыв между границами для общего случая и для случая уникальной выполнимости при k 2 {3, 4} связан со слабостью анализа; было высказано предположение, что асимптотические границы для случая уникальной выполнимости выполняются в общем случае для всех k. Если это предположение верно, из него следует, что ResolveSat оказывается быстрее любого существующего алгоритма и в случае k = 3.

В таблице представлен показатель c, используемый в значении границы 2c"~oW для уникального и общего случаев задачи k-КНФ, решаемой при помощи алгоритма ResolveSat, границы для k-КНФ и алгоритма Шонинга [ ], его улучшенной версии для 3-КНФ [1, 5, 11] и гибридной версии из работы [6]