Número máximo de literales positivos en 2SAT

Question

Max 2SAT es NP completo.

En lugar de satisfacer el número máximo de cláusulas, tengo una fórmula 2SAT totalmente satisfecha y quiero tener el número máximo de literales positivos en la asignación (de manera que todas las cláusulas estén satisfechas, por supuesto).

¿Cuál es la dificultad de este problema?

Answer 1

Este problema es NP-HARD (y, además, difícil de aproximar y W [1] -Hard), porque el conjunto máximo independiente se puede reducir a él.Reducción: Cada variable representa un vértice y cada cláusula representa un borde.