Polynomzeitzähler der Lösungen von 2sat-Expression mit reinen Literalen

Question

Gibt es in dem Titel, dass der Polynom-Zeit-Algorithmus die Anzahl der erfüllenden Argumente für einen 2sat-Ausdruck mit reinen Literalen zählt?Ein noch flacher Fall: Gibt es einen solchen Zähler, wenn die Literale im Ausdruck entweder alle positiv sind oder alle negativ sind?

Answer 1

Zählen der Anzahl der erfüllenden Zuordnungen in einer positiven 2sat-Formel ist derselbe wie das Zählen der Anzahl von Vertexabdeckungen in der entsprechenden Grafik (nach dem Entfernen von Singleton-Klauseln).Zählen der Anzahl der Scheitelpunktabdeckungen ist bekannt als $ \ mathsf {\ # P} $ -Complete.Siehe auch Diese Frage auf der CSTheory.