Максимальное количество положительных литералов в 2SAT

Question

max 2sat - это NP.

вместо того, чтобы удовлетворять максимальному количеству пунктов, у меня полностью удовлетворяемая формула 2SAT, и я хочу иметь максимальное количество положительных литералов в присваивании (такому, что все пункты удовлетворены, конечно же).

Что такое сложность этой проблемы?

Answer 1

Эта проблема входит в NP-HARD (и, кроме того, трудно приблизиться и w [1] -hard), поскольку максимальный независимый набор может быть уменьшен к нему.Уменьшение: каждая переменная представляет вершину, и каждая пункт представляет собой край.