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

Результат Шонинга был улучшен в серии статей [1, 3, 9], основанных на идее из [3]. В частности, сочетание алгоритма RandomWalk с алгоритмом 2-КНФ с полиномиальным временем выполнения позволило выбирать более подходящие начальные присваивания. Дерандомизация алгоритма SCH описана в работе [2]. В работе [4] была предложена нетривиальная комбинация SCH с еще одним известным представителем семейства алгоритмов с возвратом [8], что позволило ускорить выполнение алгоритма до показателя O(1,324n). Самый быстрый известный на данный момент алгоритм представлен в [10], он основан на том же подходе, что и алгоритм из работы [4], и выполняется за время O(1,32216n).