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

'''Теорема 1 (i). Пусть <math>k \ge 5 \;</math>, а s(n) – функция, стремящаяся к бесконечности. Тогда для любой выполнимой формулы F в k-КНФ с n переменными верно соотношение:'''

 

'''Следовательно, '''ResolveSat'''(F, s, I) при <math>I = 2^{(1 - \frac{mu_k}{k - 1})n - O(n)}</math> имеет вероятность ошибок O(1) и время выполнения <math>2^{(1 - \frac{mu_k}{k - 1})n - O(n)}</math> на любой выполнимой формуле в k-КНФ при условии, что s(n) стремится к бесконечности достаточно медленно.'''

 

'''(ii) Для <math>k \ge 3 \;</math> те же границы действительны для случая, когда формула F является уникально выполнимой.'''