4446
правок
Точные алгоритмы решения задачи о выполнимости формулы в КНФ общего вида: различия между версиями
Материал из WEGA
Точные алгоритмы решения задачи о выполнимости формулы в КНФ общего вида (посмотреть исходный код)
Версия от 12:17, 9 июля 2020
, 9 июля 2020→Основные результаты
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) |
||
| Строка 30: | Строка 30: | ||
Теорема 1 (Хирш [8]). Задачу SAT можно решить за время | Теорема 1 (Хирш [8]). Задачу SAT можно решить за время | ||
1. | |||
2. | 1. <math>|F|^{O(1)} \cdot 2^{0,30897m};</math> | ||
2. <math>|F|^{O(1)} \cdot 2^{0,10299l}.</math> | |||
