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

13

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:FSFO

  1. Die Kardinalität der Menge (dh die Anzahl der Lösungen von ).SF
  2. Bei einer Variablen : x
    • Die Anzahl der Lösungen in die das positive Literal .Sx
    • Die Anzahl der Lösungen in die das negative Literal enthalten .S¬x
  3. Bei 2 Variablen und : x1x2
    • Die Anzahl der Lösungen in die .Sx1x2
    • Die Anzahl der Lösungen in die .Sx1¬x2
    • Die Anzahl der Lösungen in die .S¬x1x2
    • Die Anzahl der Lösungen in die .S¬x1¬x2

Beachten Sie, dass das Orakel "begrenzt" ist: Es funktioniert nur für , es kann nicht für eine Formel .F F FOFFF


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 ?x1x2x3S¬x1¬x2¬x3FO

Hinweis:

Sie können in der Frage durch eine der 8 möglichen Kombinationen von , , ersetzen . Das Problem würde gleich bleiben.¬x1¬x2¬x3x1x2x3


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 2x 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 2x 3SS¬x1¬x2S¬x1¬x2S¬x1¬x2x3S¬x1¬x2x3C

wobeiϕ=1.618033 ...der goldeneSchnittist. BedingungCscheint wie folgt zu sein:"x1,x2,x3werden inFfast gleich oft erwähnt".|S¬x1¬x2||S¬x1¬x2x3|ϕ

ϕ=1.618033...Cx1x2x3F

Giorgio Camerani
quelle
1
Wenn Sie "Lösungen mit dem negativen Literal -x" sagen, meinen Sie damit "Lösungen mit x = 0"?
Noam
@Noam: Ja genau.
Giorgio Camerani
1
Einfache Beobachtung: Da die Anzahl der möglichen Fragen an das Orakel O polynomisch begrenzt ist, können Sie ohne Verlust der Allgemeinheit alle Fragen am Anfang eines Algorithmus abfragen. Daher können wir das Orakel durch zusätzliche Eingaben ersetzen, mit dem Versprechen, dass diese Zahlen korrekt sind. Ich denke, dass diese Versprechensformulierung etwas einfacher ist, als sie als Orakel zu betrachten.
Tsuyoshi Ito
@ Tsuyoshi: Ja, ich stimme dir zu.
Giorgio Camerani
1
@vzn: Die Entscheidungsversion von 2CNF ist in . Dies ist die Zählung Version des monotonen Fall (da eine monotone 2CNF Formel F , müssen Sie berechnen , wie viele erfüllenden Belegungen hat). PF
Giorgio Camerani

Antworten:

5

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 .TSIS=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 .k3x1,...,xk,vGx1,...,xk,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.GGGx1,...,xk,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.e1,...,emGke1,...,ekGk+1GkG02|G|

Colin McQuillan
quelle
Ich würde es vorziehen, diese empirische Tatsache nicht zu verwenden! Ich bevorzuge natürlich die genaue Anzahl. Aber im Übrigen habe ich das bemerkt, als ich versucht habe, die genaue Anzahl zu bestimmen.
Giorgio Camerani
Danke für deine Antwort. Ja, es ist schwer: Wie Sie sagen, würde eine positive Antwort auf diese Frage #P = FP implizieren.
Giorgio Camerani
7

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.2n3

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 | ?Sx1|S|

András Salamon
quelle
2
In der Tat müssen die gegebenen Informationen stark genug sein, um die zugrunde liegende Härte zu überwinden. Es ist bekannt, dass es für monotone 2-SAT-Lösungen kein fpras gibt, es sei denn, NP = RP.
mhum
@Andras: Was hier „Orakel“ genannt wird , ist nur eine Art Wörterbuch . Es scheint der Fall zu sein, dass ein solches Wörterbuch D inkrementell erstellt werden kann, indem es jedes Mal aktualisiert wird, wenn eine neue Klausel zu F hinzugefügt wird . Das Problem ist, dass ich diese Frage beantworten muss, um D korrekt zu aktualisieren . DDFD
Giorgio Camerani
@Walter: Ja, das verstehe ich. Mein Punkt ist, dass sogar ein viel einfacher Fall nicht klar ist: von der Gesamtzahl der Lösungen zu der Zahl der Lösungen, die ein einzelnes Literal enthalten.
András Salamon
1
Möglicherweise ist Ihre Formel im Wesentlichen linear: Unabhängige Mengen in einem Pfad folgen der Fibonacci-Sequenz. Eine Möglichkeit, dies zu sehen, besteht darin, dass die Partitionsfunktion (1 1; 1 0) phi als Eigenwert hat.
Colin McQuillan
3
Ich habe zufällig einige Folien gefunden, auf denen ein strengeres Ergebnis diskutiert wurde : isid.ac.in/~antar/Talks/Counting-Hard-Core_KBS_slides.pdf (siehe Seite 11)
Colin McQuillan