2SAT中的最大积极文字数

Question

max 2sat是NP完成。

而不是满足最大条款数，我有一个完全满足的2SAT公式，我希望在分配中拥有最大数量的积极文字（例如，当然，所有条款都满足）。

这个问题的难度是什么？

Answer 1

此问题是NP-Hard（并且还难以近似，并且W [1] - 哈达），因为可以减少到它的最大独立集。缩减：每个变量代表顶点，每个子句代表边缘。