Ce cas est-il du 2SAT NP-complete 2SAT?
-
04-11-2019 - |
Question
2SAT pondéré demande s'il est possible de satisfaire la formule avec au plus les variables $ k $ définies comme positives / négatives. Trivialement, chaque instance doit être en 2CNF. Il est connu pour être $ mathsf {np} $ - complet.
Nous avons suivi une restriction supplémentaire: chaque variable apparaît deux fois plus positive et une fois comme négative ou vice versa.
Exemple d'instance:
$ (x lor y) land (x lor z) land ( overline x lor t) land ( overline y lor z) land ( overline y lor overline t) land ( overline z lor overline t) $
Est-ce que cette variante 2SAT pondérée $ mathsf {np} $ - complète?
Bien sûr, si le sommet couvre où chaque sommet n'a que 2 arêtes est $ mathsf {np} $ - dur, cela doit également être $ mathsf {np} $ - dur. Donc, si ce résultat est connu, alors cela peut également être une réponse. Ah, eh bien, cela n'aide pas.
Pas de solution correcte