Ce cas est-il du 2SAT NP-complete 2SAT?

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.