Número máximo de literales positivos en 2SAT
-
29-09-2020 - |
Pregunta
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?
Solución
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.
Licenciado bajo: CC-BY-SA con atribución
No afiliado a cs.stackexchange