Laboratory of Mathematical Logic at PDMI

Пятница, 30 ноября, ауд. 106. Начало в 14:00.

Докладчик: Татьяна Белова.

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

Abstract

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