Точные алгоритмы решения задачи о выполнимости формулы в КНФ общего вида: различия между версиями

Перейти к навигации Перейти к поиску
Строка 30: Строка 30:


Теорема 1 (Хирш [8]). Задачу SAT можно решить за время
Теорема 1 (Хирш [8]). Задачу SAT можно решить за время
1. jFjO(1). 2°:30897m;
 
2. jFjO(1) • 20:10299
1. <math>|F|^{O(1)} \cdot 2^{0,30897m};</math>
 
2. <math>|F|^{O(1)} \cdot 2^{0,10299l}.</math>




Источник — http://pco.iis.nsk.su/wega/index.php/Точные_алгоритмы_решения_задачи_о_выполнимости_формулы_в_КНФ_общего_вида