Eingeschränkte monotone 3CNF-Formel: Zählen zufriedenstellender Zuordnungen (sowohl Modulo

Betrachten Sie eine monotone 3CNF-Formel mit den folgenden zusätzlichen Einschränkungen:

• Jede Variable erscheint in genau Klauseln.$2$
• Bei beliebigen Klauseln teilen sie höchstens 1 Variable.$2$$1$

Ich würde gerne wissen, wie schwer es ist, die zufriedenstellenden Aufgaben einer solchen Formel zu zählen.

Update 06/04/2013 12:55

Ich würde auch gerne wissen, wie schwer es ist, die Parität der Anzahl zufriedenstellender Aufgaben zu bestimmen.

Update 11/04/2013 22:40

Was ist, wenn wir zusätzlich zu den oben beschriebenen Einschränkungen auch die folgenden Einschränkungen einführen:

• Die Formel ist planar.
• Die Formel ist zweiteilig.

Update 16/04/2013 23:00

$3$$\#P$$\oplus P$-hard auch nicht.

Update 09/06/2013 07:38

$\oplus P$

In jedem Diagramm ist die Parität der Anzahl der Scheitelpunktabdeckungen gleich der Parität der Anzahl der Kantenabdeckungen.

$|C|$$\Delta_{|V|} = O_{|V|} - E_{|V|}$$O_{|V|} + E_{|V|}$

$\oplus$$\oplus$

Zumindest die zweite Hälfte der Frage ist geklärt.

Ihr Problem ist wahrscheinlich # P-vollständig, obwohl ich es in der Literatur nicht finden konnte.

Eine andere Möglichkeit, Ihr Problem zu benennen, ist "# 3-Regular-Edge-Cover". Konstruieren Sie anhand einer Formel ein Diagramm, in dem jede Klausel einem Scheitelpunkt und jede Variable einer Kante entspricht. Da die Formel ein 3CNF ist, ist der Graph 3-regulär (oder hat je nach Definition den maximalen Grad 3). Darüber hinaus ist die Grafik einfach. Eine zufriedenstellende Aufgabe entspricht einer Kantenabdeckung.

Hier sind einige verwandte Probleme:

• # 1-Ex3MonoSat ist # P-vollständig . Dies ist dasselbe wie Ihr Problem, nur eine zufriedenstellende Lösung muss genau eine Variable in jeder Klausel erfüllen.
• Das Zählen der Anzahl der Scheitelpunktabdeckungen in 3 regulären planaren Graphen ist # P-vollständig .
• Es gibt ein FPRAS für die Abdeckung mit der regulären Kante Nr. 3 . Dies legt nahe, dass die Autoren glauben, dass das Problem schwierig ist.