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

13

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.¬UNEUNE

Mohemnist
la source

Réponses:

20

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.

loup
la source