Compteur de temps polynomial de solutions d'expression 2Sat avec des littéraux purs

Question

Selon le titre, existe-t-il un algorithme de temps polynomial pour compter le nombre d'arguments satisfaisants pour une expression 2SAT avec des littéraux purs?Un boîtier encore moins profond: y a-t-il un tel compteur lorsque les littéraux dans l'expression sont soit tous positifs, soit tout négatif?

Answer 1

Compter le nombre de missions satisfaisantes dans une formule positive 2SAT est la même que celle du nombre de couvercles de sommet dans le graphique correspondant (après avoir retiré les clauses singleton).Compter le nombre de couvertures de sommet est connu pour être $ \ mathsf {\ # p} $ -Compléte.Voir aussi Cette question sur cstheary.