4430
правок
K-КНФ-алгоритмы на основе поиска с возвратом: различия между версиями
Материал из WEGA
K-КНФ-алгоритмы на основе поиска с возвратом (посмотреть исходный код)
Версия от 19:09, 25 февраля 2018
, 25 февраля 2018→Основные результаты
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) |
||
| Строка 122: | Строка 122: | ||
Легко показать, что <math>\mu_3 = 4 - 4 \; ln \; 2 > 1,226</math>, применив разложение функции ln 2 в ряд Тейлора. Используя стандартные способы, также легко показать, что <math>\mu_k \;</math> представляет собой возрастающую функцию от k с пределом <math>\sum_{j=1}^{\infty} (1 / j^2) = (\pi^2 / 6) = 1,644</math>. | Легко показать, что <math>\mu_3 = 4 - 4 \; ln \; 2 > 1,226</math>, применив разложение функции ln 2 в ряд Тейлора. Используя стандартные способы, также легко показать, что <math>\mu_k \;</math> представляет собой возрастающую функцию от k с пределом <math>\sum_{j=1}^{\infty} (1 / j^2) = (\pi^2 / 6) = 1,644...</math>. | ||
| Строка 130: | Строка 130: | ||
'''Теорема 1 (i). Пусть <math>k \ge 5 \;</math>, а s(n) – функция, стремящаяся к бесконечности. Тогда для любой выполнимой формулы F в k-КНФ с n переменными верно соотношение:''' | '''Теорема 1 (i). Пусть <math>k \ge 5 \;</math>, а s(n) – функция, стремящаяся к бесконечности. Тогда для любой выполнимой формулы F в k-КНФ с n переменными верно соотношение:''' | ||
<math>\tau(F_s) \ge 2^{-(1 - \frac{mu_k}{k - 1})n - o(n)}</math>. | <math>\tau(F_s) \ge 2^{-(1 - \frac{\mu_k}{k - 1})n - o(n)}</math>. | ||
'''Следовательно, '''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) стремится к бесконечности достаточно медленно.''' | |||
'''Следовательно, '''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 является уникально выполнимой.''' | '''(ii) Для <math>k \ge 3 \;</math> те же границы действительны для случая, когда формула F является уникально выполнимой.''' | ||
