Was sind die # P-vollständigen Unterfamilien von # 2-SAT?

Kurze Version.

Der Beweis , dass Original # 2-SAT ist #P -komplette zeigt in der Tat, dass diese Instanzen von # 2-SAT die beide monotone (nicht unter Einbeziehung der Negationen aller Variablen) und bipartite (der Graph durch die Klauseln über die geformte Variablen ist ein zweigliedriger Graph) sind # P-hart. Somit sind die beiden Sonderfälle # 2-MONOTONE-SAT und # 2-BIPARTITE-SAT #P -hart. Gibt es noch andere Sonderfälle, die sich durch "natürliche" Eigenschaften der Formel charakterisieren lassen, die auch # P-hart sind?

Lange Version.

Das Problem # 2-SAT ist die Aufgabe der Berechnung - für eine Boolesche Formel die aus der Verknüpfung mehrerer Klauseln besteht, wobei jede Klausel eine Disjunktion zweier Literale x j oder ˉ x j ist - der Anzahl der Booleschen Zeichenfolgen x ∈ { 0 , 1 } n, so dass ϕ ( x ) = 1 ist . Herausfinden, ob es existiert eine solche x ist einfach; aber die Anzahl der Lösungen im allgemeinen zu zählen ist #P -komplette, wie gezeigt in Valiant$\phi$$x_j$$\bar x_j$$x \in \{0,1\}^n$$\phi(x) = 1$$x$Die Komplexität von Aufzählungs- und Zuverlässigkeitsproblemen, SIAM J. Comput., 8 , S. 410–421 .

Insbesondere für den Fall von # 2-SAT zeigt Valiant tatsächlich eine Reduktion auf # 2-SAT durch Zählen von Übereinstimmungen (einschließlich unvollständiger) in zweigeteilten Graphen, was zu Instanzen von # 2-SAT mit einer ganz bestimmten Struktur führt , wie folgt.

1. Erstens ist zu beachten , dass die monotone Problem äquivalent ist, durch Substitution, um das Problem , in dem für jede Variable , entweder x j in der Formel auftritt φ oder ˉ x j tut , aber nicht beides. Insbesondere ist das "monoton abnehmende" Problem, bei dem nur die Negationen ˉ x j für jede Variable auftreten, genau so schwierig wie der monotone Fall.$x_j$$x_j$$\phi$$\bar x_j$$\bar x_j$

2. Für jeden Graphen mit m Kanten können wir eine monoton abnehmende 2-SAT-Formel konstruieren, die Übereinstimmungen - Sammlungen von Kanten ohne gemeinsame Eckpunkte - entspricht, indem wir jeder Kante, die repräsentiert , eine Variable x e zuweisen ob es in einer Kantenmenge enthalten ist; die Eigenschaft einer Menge M ⊆ E , die eine Übereinstimmung ist, ist äquivalent zu dem Inzidenzvektor x = χ M , der die CNF-Formel ϕ erfüllt, deren Klauseln gegeben sind durch ( ˉ x e ∨ ˉ x f$G = (V,E)$$m$$x_e$$M \subseteq E$$\mathbf x = \chi_M$$\phi$$(\bar x_e \vee \bar x_f)$für jedes Kantenpaar die einen Scheitelpunkt teilen. Konstruktionsbedingt hat ϕ so viele befriedigende Lösungen x ∈ { 0 , 1 } m, wie es (möglicherweise unvollständige) Übereinstimmungen im Graphen G gibt .$e, f \in E$$\phi$$\mathbf x \in \{0,1\}^m$$G$

3. Wenn der Graph für den wir die Übereinstimmungen zählen möchten, zweiteilig ist, enthält er keine ungeraden Zyklen - was wir als eine Folge von Kanten im Graph beschreiben können, die mit derselben Kante beginnt und endet (ohne diese letzte Kante zweimal zu zählen). . Dann gibt es keine Sequenz von Variablen x e , x f , x g , ... , x e ungerader Länge in φ , in der benachbarten Variablen in einem gemeinsamen Abschnitt beteiligt ist. Dann wäre die Formel ϕ in der zuvor beschriebenen Weise zweiteilig.$G$$x_e, x_f, x_g, \ldots, x_e$$\phi$$\phi$

4. Insbesondere das Zählen der Anzahl von Übereinstimmungen in willkürlichen zweigliedrigen Graphen kann verwendet werden, um die Anzahl von perfekten Übereinstimmungen in einem zweigliedrigen Graphen zu zählen: vorausgesetzt, ein Eingangs-Bitrarit-Graph mit zwei zweigliedrigen Partitionen A , B der Bei gleicher Größe n kann man Graphen G k erzeugen, indem man A mit 0 ≤ k ≤ n zusätzlichen Scheitelpunkten erweitert, die mit allen Scheitelpunkten von B verbunden sind . Weil alle Übereinstimmungen in $G = (A \cup B, E)$$A, B$$n$$G_k$$A$$0 \leqslant k \leqslant n$$B$$G$eine gegebene Größe beiträgt unterschiedlich zu der Anzahl der in passenden durch diesen ein Zählen der Anzahl des in passenden bestimmen kann G der Größe n (das heißt, die perfekt passenden sind); und beachte, dass das Zählen der Anzahl perfekter Übereinstimmungen in zweigeteilten Graphen gleichbedeutend ist mit der Berechnung von Permanenten von { 0 , 1 } -Matrizen durch eine einfache Korrespondenz.$G_k$$G$$n$$\{0,1\}$

Die Klasse von Instanzen von # 2-SAT, die als # P- hart gezeigt werden, sind dann die monotonen bipartiten Instanzen.

Frage: Was sind die besonderen Fälle von # 2-SAT, die #P -komplette, als Folge dieser oder einer anderen Reduktion?

Es wäre interessant, wenn die Menschen nicht nur eine Reduktion aufzeigen / zitieren, sondern auch einen intuitiven Grund dafür beschreiben könnten, wie der Sonderfall natürliche Ansätze für das Zählen der Satsifying-Aufgaben behindern könnte. Zum Beispiel, obwohl MONOTONE-2-SAT trivial lösbar ist ( ist immer eine Lösung), sind monotone Instanzen diejenigen, bei denen das Zuweisen einer Variablen zu einem festen Wert routinemäßig viele Einschränkungen für die verbleibenden Variablen auferlegt. Das Fixieren einer Variablen x j = 0 schränkt nur die Werte der Variablen ein, die durch eine Klausel unmittelbar damit verbunden sind. und Einstellen x j = $\mathbf x = 1^n$$x_j = 0$$x_j = 1$schränkt die möglichen Werte anderer Variablen überhaupt nicht ein. (Es ist nicht klar, dass die vergleichbare Einschränkung für zweigliedrige Diagramme in gleicher Weise von Bedeutung ist. Die zweigliedrige Einschränkung fügt offenbar Struktur hinzu, anstatt sie zu entfernen, fügt jedoch keine Struktur hinzu, die effizient gezählt werden kann.)

Zum Hinzufügen bearbeitet. Bonuspunkte für eine solche Klasse vergeben werden , die nicht letztlich stützen sich auf die Existenz von monotone Instanzen (wie # 2-bipartiter-SAT oben der Fall ist, deren Härte offenbar aufgrund der Einbeziehung des #P -hard Sonderfall # 2 -MONOTONE-BIPARTITE-SAT). Zum Beispiel wäre ein Argument für die Härte von # 2-BIPARTITE-SAT interessant, das sich nicht auf monotone Instanzen stützt (sondern sich möglicherweise auf eine andere Unterfamilie stützt).

# 3-Regular Bipartite Planar Vertex Cover ist # P-Complete

Da das Zählen von Vertex-Covers genau das Gleiche ist wie das Zählen von erfüllenden Zuweisungen einer monotonen # 2-SAT-Instanz, impliziert das obige Ergebnis, dass es # P-vollständig ist, um erfüllende Zuweisungen einer # 2-SAT-Instanz zu zählen, die monoton und 3-regulär ist und zweiteilig und planar .

Dies bedeutet wiederum, dass zusätzlich zu den beiden bereits in der Frage genannten Sonderfällen # 2-MONOTONE-SAT und # 2-BIPARTITE-SAT die beiden Sonderfälle # 2-CUBIC-SAT und # 2-PLANAR-SAT vorliegen # P-komplett auch.