Разрешаемые экземпляры Max-Sat за полиномиальное время

18

Задача Max-Sat просит вас найти назначение формулы CNF, которое удовлетворяет как можно большему количеству предложений.

Для более простой задачи SAT существует много известных частных случаев, которые могут быть решены за полиномиальное время, например, мы можем решить 2-SAT за полиномиальное время.

Для Max-Sat ситуация иная, так как Max-Sat является NP-сложным даже для формул 2-CNF (каждое предложение содержит только 2 переменные).

Есть ли какие-нибудь интересные специальные входы, для которых Max-Sat является полиномиальным?

В частности, я был бы заинтересован в стандартной справочной информации для решения Max-Sat, когда графа возрастания имеет ограниченную ширину дерева.

Мартин Ватшелле
источник
3
Планарный max-cut является частным случаем max-cut, который (в некотором смысле) является частным случаем max-2-sat.
Юкка Суомела

Ответы:

6

Это не отвечает непосредственно на вашу проблему Max-SAT, но ссылки могут помочь вам получить полный ответ.

Szeider показал, что Удовлетворенность определяется с помощью фиксированных параметров при параметризации по ширине графика зависимости. Самер и Шейдер представили эффективный алгоритм динамического программирования.

Ссылки

С. Шейдер. Об фиксированных параметрируемых параметризациях SAT. В учеб. 6-я Международная конференция по теории и применениям удовлетворенности (SAT'03), Selected and Revised Papers, vol. 2919 LNCS, стр. 188–202. Springer-Verlag, 2004.

М. Самер и С. Шейдер. Алгоритмы подсчета пропозициональной модели. В учеб. 14-я Международная конференция по логике для программирования, искусственного интеллекта и рассуждения (LPAR'07), том. 4790 LNCS, стр. 484–498. Springer-Verlag, 2007.

Самер и Шейдер, Трактабельность с фиксированными параметрами. В А. Бире, М. Хейле, Х. ван Маарене и Т. Уолше, редакторы, «Справочник по удовлетворенности», часть 1, глава 13. IOS Press

Мухаммед Аль-Туркистани
источник
Я знаю некоторые работы Стефана Сзейдера, более поздняя статья показывает, что #SAT является полиномиальным, когда графа возрастания имеет ограниченную ширину клика, что также подразумевает ограниченную ширину дерева (хотя здесь у нас есть среда выполнения XP вместо FPT). Фридрих Сливовский и Стефан Шейдер. Подсчет моделей для формул ограниченной ширины клика, алгоритмы и вычисления, вып. 8283, стр. 677-687, LNCS, 2013 Я знаю, что результаты такого типа часто переводятся в MAX-SAT, но было бы намного проще иметь ссылку, где это уже сделано, вместо того, чтобы делать это самостоятельно.
Мартин Ватшелле
0

Мы нашли один вид такой собственности:

FFИксСИксСССИксИкс

см .: http://arxiv.org/abs/1402.6485

Известны ли другие подобные свойства?

Мартин Ватшелле
источник