Nombre maximum de littéraux positifs en 2SAT

Question

max 2SAT est NP complet.

Au lieu de satisfaire le nombre maximum de clauses, j'ai une formule de 2SAT entièrement satisfible et je souhaite avoir le nombre maximum de littéraux positifs dans la mission (de sorte que toutes les clauses soient satisfaites, bien sûr).

Quelle est la difficulté de ce problème?

Answer 1

Ce problème est NP-DUR (et de plus en plus approximatif pour approximativement et w [1] -hard), car un ensemble maximal indépendant peut être réduit.Réduction: chaque variable représente un sommet et chaque clause représente un bord.