Zählung der Anzahl zufriedenstellender Aufträge in einem POSITIVEN CNF-SAT

13

Wir kennen das Problem, die Anzahl der erfüllenden Zuordnungen in einer gegebenen allgemeinen Booleschen Formel (CNF-SAT), einer gegebenen DNF-Formel oder sogar einer gegebenen 2SAT-Formel zu zählen, als ein # P-vollständiges Problem.

Betrachten Sie nun ein CNF-SAT ohne negatives Literal (no , immer ). Das Entscheidungsproblem ist sehr einfach (setzen Sie alle Variablen auf TRUE und prüfen Sie, ob die Zuweisung der Formel entspricht). Hat dies einen polynomialen Zeitalgorithmus? Oder es ist ein # P-vollständiges Problem.¬EINEIN

Mohemnist
quelle

Antworten:

20

Dies ist immer noch # P-complete [1]. Dieses Problem wird normalerweise als montone (#) SAT bezeichnet. Monotone # 2-SAT ist bereits # P-vollständig (dies entspricht dem Zählen der Scheitelpunktabdeckungen eines Graphen).

[1] Roth, Dan. "Über die Härte des ungefähren Denkens." Artificial Intelligence 82.1-2 (1996): 273-302.

holf
quelle