Вы здесь

Алгоритмы для NP-трудных задач (2013). Лекция 10

Лекция
Предмет:
Дата записи:
10.11.13
Дата публикации:
10.11.13
Код для блога:

Алгоритмы для задачи выполнимости: метод расщепления

DPLL-алгоритмы, основные идеи метода расщепления, вектор и число расщепления. O∗(22n/3) для задачи 3-выполнимости одновыполнимой формулы через расщепление относительно случайной перестановки. Запоминание дизъюнктов: решение задачи выполнимости на формулах константной плотности за O∗((2-c)n). Комбинированные меры сложности, measure and conquer: O∗(22m/5.5) для задачи максимальной 2-выполнимости.

Страница лекции на сайте Computer Science Club

Другие лекции курса

12