Максимальное количество положительных литералов в 2SAT
-
29-09-2020 - |
Вопрос
max 2sat - это NP.
вместо того, чтобы удовлетворять максимальному количеству пунктов, у меня полностью удовлетворяемая формула 2SAT, и я хочу иметь максимальное количество положительных литералов в присваивании (такому, что все пункты удовлетворены, конечно же).
Что такое сложность этой проблемы?
Решение
Эта проблема входит в NP-HARD (и, кроме того, трудно приблизиться и w [1] -hard), поскольку максимальный независимый набор может быть уменьшен к нему.Уменьшение: каждая переменная представляет вершину, и каждая пункт представляет собой край.
Не связан с cs.stackexchange