Compter le nombre d'assignations satisfaisantes dans un CNF-SAT POSITIF

Nous savons que le problème du comptage du nombre d'affectations satisfaisantes dans une formule booléenne générale donnée (CNF-SAT), une formule DNF donnée, ou même une formule 2SAT donnée est un problème # P-complet .

Maintenant, considérons un CNF-SAT sans littéral négatif (pas de , toujours A ). Le problème de décision est très facile (réglez toutes les variables sur VRAI et vérifiez si l'affectation satisfait la formule), mais qu'en est-il du comptage du nombre d'affectations satisfaisantes? Est-ce que cela a un algorithme de temps polynomial? Ou c'est un problème # P-complet.$\neg A$$A$

Ceci est toujours # P-complet [1]. Ce problème est généralement appelé montone (#) SAT. Le monotone # 2-SAT est déjà # P-complet (cela équivaut à compter les couvertures des sommets d'un graphique).

[1] Roth, Dan. "Sur la dureté du raisonnement approximatif." Intelligence artificielle 82.1-2 (1996): 273-302.

Ce problème est Monotone-SAT. C'est # P-Complete sous Cook Reductions. C'est l'un de ces problèmes qui sont «faciles à décider mais difficiles à compter». Je recommande le papier suivant. Auto-réductibilité des problèmes de comptage dur avec la version de décision dans P