Zähllösungen von Monotone-2CNF-Formeln

Eine Monotone-2CNF-Formel ist eine CNF- Formel, bei der jeder Satz aus genau 2 positiven Literalen besteht.

Jetzt habe ich eine Monotone-2CNF Formel . Sei die Menge von befriedigenden Zuordnungen. Ich habe auch ein Orakel , das folgende Informationen liefern kann:$F$$S$$F$$O$

1. Die Kardinalität der Menge (dh die Anzahl der Lösungen von ).$S$$F$
2. Bei einer Variablen : $x$
   • Die Anzahl der Lösungen in die das positive Literal .$S$$x$
   • Die Anzahl der Lösungen in die das negative Literal enthalten .$S$$\lnot x$
3. Bei 2 Variablen und : $x_1$$x_2$
   • Die Anzahl der Lösungen in die .$S$$x_1 \land x_2$
   • Die Anzahl der Lösungen in die .$S$$x_1 \land \lnot x_2$
   • Die Anzahl der Lösungen in die .$S$$\lnot x_1 \land x_2$
   • Die Anzahl der Lösungen in die .$S$$\lnot x_1 \land \lnot x_2$

Beachten Sie, dass das Orakel "begrenzt" ist: Es funktioniert nur für , es kann nicht für eine Formel .F F ′ ≠ $O$$F$$F' \neq F$

Frage:

Angesichts 3 Variablen , , ist es möglich , die Anzahl der Lösungen in bestimmen enthalten in Polynomialzeit, mit und die Informationen zur Verfügung gestellt von ?$x_1$$x_2$$x_3$$S$$\lnot x_1 \land \lnot x_2 \land \lnot x_3$$F$$O$

Hinweis:

Sie können in der Frage durch eine der 8 möglichen Kombinationen von , , ersetzen . Das Problem würde gleich bleiben.$\lnot x_1 \land \lnot x_2 \land \lnot x_3$$x_1$$x_2$$x_3$

Empirische Tatsache:

Vor einer Woche bin ich auf die folgende empirische Tatsache gestoßen. Sei die Menge der Lösungen, die , und sei Sei die Menge der Lösungen, die ¬ x 1 ∧ ¬ x 2 ∧ x 3 enthalten . Nun scheint es so zu sein, dass, wenn Bedingung C zutrifft, auch diese Beziehung zutrifft: | S ¬ x 1 ∧ ¬ x 2 |¬ x 1 ∧ ¬ x 2 S ¬ x 1 ∧ ¬ x 2 ∧ x 3 ⊂ $S_{\lnot x_1 \land \lnot x_2} \subset S$$\lnot x_1 \land \lnot x_2$$S_{\lnot x_1 \land \lnot x_2 \land x_3} \subset S$$\lnot x_1 \land \lnot x_2 \land x_3$$C$

wobeiϕ=1.618033 ...der goldeneSchnittist. BedingungCscheint wie folgt zu sein:"x1,x2,x3werden inFfast gleich oft erwähnt".$\frac{|S_{\lnot x_1 \land \lnot x_2}|}{|S_{\lnot x_1 \land \lnot x_2 \land x_3}|} \simeq \phi$

$\phi = 1.618033...$$C$$x_1$$x_2$$x_3$$F$

Um diese empirische Tatsache zu nutzen, möchten Sie wirklich wissen, ob ungefähre Zahlen andere ungefähre Zahlen ergeben können. Aber für den genauen Fall denke ich, dass es einen direkten Weg gibt, um zu zeigen, dass dies schwierig ist. Hier ist eine Skizze.

Beachten Sie zunächst, dass erfüllende Zuordnungen unabhängigen Mengen in einem Diagramm entsprechen. Ich werde den Ausdruck "S-Projektionen von I (G)" verwenden, um die Funktionsabbildung auf die Anzahl der unabhängigen Mengen I mit I ∩ S = T zu beschreiben . Die "k-Projektionen" sind die S-Projektionen für alle Teilmengen S von V mit | S | = k .$T \subset S$$I \cap S = T$$|S|=k$

Beweiskontur:

1. Wenn 2-Projektionen 3-Projektionen ergeben, ergeben sie auch k-Projektionen in polytime für jedes k.
2. Wenn 2-Projektionen 4-Projektionen ergeben, ist die Anzahl der unabhängigen Sätze eines Graphen in FP, also FP = # P.

(1) Sei so dass (k-1) -Projektionen k-Projektionen ergeben. Bei einem gegebenen Graphen, dessen k-Projektionen, und x 1 , . . . , X k , v ∈ G , werden wir die Projektionen auf berechnen , x 1 , . . . , x k , v .$k\geq 3$$x_1,...,x_k,v \in G$${x_1,...,x_k,v}$

Definieren Sie den Graphen indem Sie einen neuen Eckpunkt an v anhängen. Dies kann als Gewichtung von v angesehen werden. Die (k-1) -Projektionen von G ' können berechnet werden, weil wir die k-Projektionen von G kennen k-Projektionen von G ′ . Und das gibt x 1 , . . . , x k , v -Projektionen von G.$G'$$G'$$G'$${x_1,...,x_k,v}$

(2) Da ein Graph, der Reihenfolge die Kanten und definieren G k Kanten haben e 1 , . . . , E k . Die 2-Projektionen von G k + 1 können aus den 4-Projektionen von G k berechnet werden . Die Anzahl der unabhängigen Mengen in G 0 beträgt 2 | G | . Iterativ können die 4-Projektionen von G in Polynomzeit berechnet werden.${e_1,...,e_m}$$G_k$${e_1,...,e_k}$$G_{k+1}$$G_k$$G_0$$2^{|G|}$

Einige Beobachtungen, keine Antwort.

Neben dem Hinweis auf die Frage kann jede Kombination von 3 Literalen als jede andere Kombination von Literalen mit denselben Variablen ausgedrückt werden, zusammen mit einer kleinen Anzahl von Begriffen, die das Orakel bereitstellen kann. Dies ergibt sich aus der Betrachtung des Venn-Diagramms von 3 sich überschneidenden Mengen und dem Ausdrücken jeder der 8 Regionen in Bezug auf die anderen Regionen. Beachten Sie, dass die Formel hierfür weder monoton noch 2CNF sein muss.

Es ist auch klar, dass die Anzahl der Lösungen, die eine 3-Literal-Konjunktion erfüllen, als die Summe von Termen ausgedrückt werden kann, von denen jeder entweder 0 oder 1 ist und eine bestimmte Zuordnung zu allen Variablen ausdrückt. Jedes von diesen kann in linearer Zeit ausgewertet werden, es sind jedoch exponentiell viele Terme zu bewerten, so dass dies die Anforderungen nicht erfüllt.$2^{n-3}$

Daher ist die Frage wirklich, ob es möglich ist, die Eigenschaft des monotonen 2CNF auszunutzen, um diesen Ausdruck der Exponentialgröße auf die Polynomgröße zu komprimieren.

Ich habe versucht, eine einfachere Frage zu betrachten und das Orakel auf einen Hinweis mit der Anzahl der Lösungen zu beschränken, wenn die Zählungen für einzelne oder paarweise wörtliche Kombinationen nicht verfügbar sind. Ich kann keine Möglichkeit finden, das Wissen über die Anzahl der Lösungen zu nutzen, um eine schnelle Berechnung der Anzahl der Lösungen in Bezug auf ein einzelnes Literal zu erhalten.

Gibt es etwas an monotonem 2CNF, das es erlauben würde, die Anzahl der Lösungen in mit x 1 schnell zu erhalten, wenn man wüsste, | S | ?$S$$x_1$$|S|$