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

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

{| class="wikitable"

|  

|}

''В таблице представлен показатель c, используемый в значении границы <math>2^{cn - o(n)} \;</math> для уникального и общего случаев задачи k-КНФ, решаемой при помощи алгоритма ResolveSat, границы для k-КНФ и алгоритма Шонинга [12], его улучшенной версии для 3-КНФ [1, 5, 11] и гибридной версии из работы [6]''