K-КНФ-алгоритмы на основе поиска с возвратом: различия между версиями
Перейти к навигации
Перейти к поиску
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) |
||
| Строка 97: | Строка 97: | ||
Для доказательства теоремы 1 вначале рассмотрим случай уникальной выполнимости, а затем свяжем с ним задачу общего вида. При k > | Для доказательства теоремы 1 вначале рассмотрим случай уникальной выполнимости, а затем свяжем с ним задачу общего вида. При <math>k \ge 5 \;</math> из анализа следует, что асимптотика для общего случая оказывается не хуже асимптотики для случая уникальной выполнимости. При k = 3 и k = 4 границы в общем случае оказываются несколько более худшими по сравнению с уникальным. | ||
Теорема 2. Пусть s = s(n) – медленно растущая функция. Для любой выполнимой 3-КНФ-формулы с n переменными | '''Теорема 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 переменными | '''Теорема 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>.''' | ||
== Применение == | == Применение == | ||