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

'''Теорема 2. Пусть s = s(n) – медленно растущая функция. Для любой выполнимой 3-КНФ-формулы с n переменными верно <math>\tau(F_s) \ge 2^{-0,521^n}</math>, в силу чего '''ResolveSat'''(F, s, I) с <math>I = n \; 2^{0,521n}</math> имеет вероятность ошибки O(1) и время выполнения <math>2^{0,521 n + O(n)} \;</math>.'''

'''Теорема 3. Пусть s = s(n) – медленно растущая функция. Для любой выполнимой 4-КНФ-формулы с n переменными верно <math>\tau(F_s) \ge 2^{-0,5625n}</math>, в силу чего '''ResolveSat'''(F, s, I) с <math>I = n \; 2^{0,5625n} \;</math> имеет вероятность ошибки O(1) и время выполнения <math>2^{0,5625n + O(n)} \;</math>.'''