Пятница 30.11. Татьяна Белова: "Верхние и нижние оценки для различных параметризаций задачи (n, 3)-MAXSAT"

Пятница 30.11. Татьяна Белова: "Верхние и нижние оценки для различных параметризаций задачи (n, 3)-MAXSAT"

Date:

Friday, November 30, 2018 - 14:00

Abstract:

Задача (n,3)-MAX-SAT является частным случаем задачи MAX-SAT с дополнительным ограничением на входную формулу, что каждая переменная встречается в формуле не более трех раз. Мы рассмотрим различные параметризации этой задачи, улучшим известные ранее верхние оценки на время решения (n,3)-MAXSAT относительно числа переменных в формуле, а также относительно числа клозов, которые мы хотим выполнить.
Кроме того, мы покажем, что выполнить хотя бы на один клоз больше, чем при тривиальном означивании, где всем переменным присваивается истина, уже является NP-трудной задачей.