Komplexität der Berechnung der Parität der zweimal gelesenen entgegengesetzten CNF-Formel ( )

In einer zweimal gelesenen entgegengesetzten CNF-Formel erscheint jede Variable zweimal, einmal positiv und einmal negativ.

Ich interessiere mich für das Problem , das darin besteht, die Parität der Anzahl zufriedenstellender Zuweisungen einer zweimal gelesenen entgegengesetzten CNF-Formel zu berechnen. $\oplus\text{Rtw-Opp-CNF}$

Ich konnte keinen Hinweis auf die Komplexität eines solchen Problems finden. Die nächstgelegene ich war in der Lage zu finden , ist , dass die Zählung Version ist -komplette (Abschnitt 6.3 live in diesem Beitrag ). $\#\text{Rtw-Opp-CNF}$ $\#\text{P}$

Vielen Dank im Voraus für Ihre Hilfe.

Update 10. April 2016

In diesem Papier , das Problem sein gezeigt -komplette jedoch die durch Reduktion hergestellt aus Formel nicht in CNF und Sobald Sie versuchen, es wieder in CNF umzuwandeln, erhalten Sie eine dreimal lesbare Formel. $\oplus\text{Rtw-Opp-SAT}$ $\oplus\text{P}$ $3\text{SAT}$
Die monotone Version wird in diesem Dokument als -vollständig dargestellt . In einem solchen wird am Ende von Abschnitt 4 schnell erwähnt: Valiant sagt, es sei entartet. Mir ist nicht klar, was Entartung genau bedeutet und was es in Bezug auf die Härte bedeutet. $\oplus\text{Rtw-Mon-CNF}$ $\oplus\text{P}$ $\oplus\text{Rtw-Opp-CNF}$

Update 12. April 2016

Es wäre auch sehr interessant zu wissen, ob jemals jemand die Komplexität des Problems hat. Bei einer zweimal gelesenen entgegengesetzten CNF-Formel muss bei einem solchen Problem die Differenz zwischen der Anzahl der erfüllenden Zuweisungen mit einer ungeraden Anzahl von Variablen, die auf true gesetzt sind, und der Anzahl der zufriedenstellenden Zuweisungen mit einer geraden Anzahl von Variablen, die auf true gesetzt sind, berechnet werden. Ich habe keine Literatur darüber gefunden. $\Delta\text{Rtw-Opp-CNF}$

Update 29. Mai 2016

Wie Emil Jeřábek in seinem Kommentar , ist es nicht wahr, dass Valiant sagte, dass das Problem entartet ist. Er sagte nur, dass eine eingeschränktere Version eines solchen Problems, , entartet ist. In der Zwischenzeit weiß ich immer noch nicht, was degeneriert genau bedeutet, aber zumindest scheint es jetzt klar zu sein, dass es ein Synonym für mangelnde Ausdruckskraft ist. $\oplus\text{Rtw-Opp-CNF}$ $\oplus\text{Pl-Rtw-Opp-3CNF}$

cc.complexity-theory ds.algorithms counting-complexity Giorgio Camerani
quelle

WRtw-Opp-CNF ist so hart wie ⊕Rtw-Mon-CNF. Sie können das Negations-Gadget erstellen: (i0 v x0 v x1) (x1 v x2) (i1 v x0 v x2). Wenn i0 = i1, dann ist Gewicht = 0 (in Modulo 2). Ansonsten Gewicht = 1.

Ich kann keine Reduktion von ⊕Rtw-Mon-CNF zu ⊕Rtw-Opp-CNF finden, aber ich habe einen Polynomalgorithmus zum Lösen von ⊕Rtw-Opp-CNF gefunden. ⊕Rtw-Opp-CNF ist also einfacher.

Ich kann ValRtw-Opp-CNF in Valiants Artikel nicht erwähnen. Er behauptet, dass ⊕Pl-Rtw-Opp-3CNF "entartet" ist, dies beinhaltet jedoch mehrere zusätzliche Einschränkungen.

Emil Jeřábek 3.0

@ EmilJeřábek: Du hast definitiv recht. Ich wurde durch meine Unkenntnis der Bedeutung von "entartet" in die Irre geführt und habe dieselbe Art von Argumentation angewendet, die normalerweise bei Vorhandensein von Vollständigkeitsergebnissen angewendet wird: Wenn ein bestimmtes Problem für eine Klasse vollständig ist, bewahrt das Entfernen von Einschränkungen offensichtlich die Vollständigkeit. Auch wenn ich immer noch nicht weiß, was "entartet" genau bedeutet, ist mir jetzt zumindest klar, dass ein solcher Begriff irgendwie ein Synonym für Schwäche ist (dh mangelnde Ausdruckskraft), weshalb die oben genannte Argumentation nicht angewendet werden kann. Ich habe die Frage entsprechend korrigiert.

Giorgio Camerani

@ Maciej: Wirklich? Wie funktioniert Ihr Polynomalgorithmus?

Giorgio Camerani

Antworten:

Es stellt sich heraus, dass jede Formel, die zweimal gegengelesen wird, eine gerade Anzahl zufriedenstellender Zuordnungen aufweist. Hier ist ein schöner Beweis dafür, obwohl man wahrscheinlich die graphentheoretische Terminologie eliminieren könnte.

Sei eine CNF-Formel, die zweimal gegengelesen wird. Ohne Verlust der Allgemeinheit enthält keine Klausel sowohl eine Variable als auch deren Negation. $\phi$

Betrachten Sie den Graphen dessen Scheitelpunktmenge die Klauseln von , und fügen Sie für jede Variable eine (ungerichtete) Kante hinzu, die auf die beiden Klauseln mit fällt . Unsere WLOG-Annahme in besagt, dass dieses Diagramm keine Selbstschleifen aufweist. Denken Sie außerdem daran, jede Kante mit der sie definierenden Variablen zu kennzeichnen. Auf diese Weise können wir zwischen parallelen Kanten unterscheiden. $G$ $\phi$ $x$ $x$ $\phi$

Eine Ausrichtung von ist ein gerichteter Graph, dessen Kanten durch Zuweisen einer Richtung zu jeder Kante in . Nennen Sie eine Ausrichtung von zulässig, wenn jeder Scheitelpunkt von eine ausgehende Kante hat. Es ist leicht zu erkennen, dass zufriedenstellende Zuordnungen zu in bijektiver Entsprechung mit zulässigen Orientierungen von . $G$ $G$ $G$ $G$ $\phi$ $G$

Jetzt behaupte ich, dass die Anzahl der zulässigen Orientierungen von ist. Das Argument ist "durch Involution": Ich konstruiere eine Karte mit den folgenden Eigenschaften: $G$ $\Phi$

$\Phi$ ist vollständig definiert (jede zulässige Ausrichtung wird irgendwo abgebildet)
$\Phi$ sendet zulässige Orientierungen an zulässige Orientierungen
$\Phi$ ist eine Involution ( ist die Identität) $\Phi \circ \Phi$
$\Phi$ hat keine Fixpunkte

Sobald diese festgelegt sind, können wir beobachten, dass die Bahnen von Größe 2 haben und die zulässigen Orientierungen von . Daraus folgt, dass die Anzahl der zulässigen Orientierungen gerade ist. $\Phi$ $G$

Um zu definieren , sei eine zulässige Orientierung und erwäge, in seine stark verbundenen Komponenten zu zerlegen. sendet dann an die Ausrichtung, die durch Umkehren aller Kanten innerhalb der stark verbundenen Komponenten gebildet wird. Die Eigenschaften werden dann einfach überprüft: $\Phi$ $\vec{G}$ $\vec{G}$ $\Phi$ $\vec{G}$

Jeder gerichtete Graph kann in stark verbundene Komponenten unterteilt werden.
Betrachten Sie die "DAG stark verbundener Komponenten" in ; Nennen wir es das Quotientendiagramm. Beachten Sie, dass dieselbe Quotientenstruktur hat, da die Kanten zwischen SCCs nicht beeinflusst und stark verbundene Diagramme stark verbunden bleiben, wenn alle Kanten umgekehrt werden. Wenn ein SCC mehr als einen Scheitelpunkt hat, haben alle seine konstituierenden Scheitelpunkte eine eingehende Kante. Wenn ein SCC nur einen einzigen Scheitelpunkt hat und keine Quelle im Quotienten ist, haben alle seine konstituierenden Scheitelpunkte eine eingehende Kante. Also um zu zeigen $\vec G$ $\Phi(\vec G)$ $\Phi$ $\Phi(\vec G)$ zulässig ist, genügt es zu zeigen, dass die SCCs, die Quellen im Quotienten sind, mehrere Eckpunkte haben. Dies folgt jedoch aus der Tatsache, dass jeder Scheitelpunkt in der Komponente eine eingehende Kante hat, die von einem anderen Scheitelpunkt in der Komponente stammen muss, da keine Selbstschleifen hat und die Komponente eine Quelle im Quotienten ist. $G$
Dies folgt aus der Tatsache, dass die Quotientenstruktur von mit der Quotientenstruktur von übereinstimmt . $\Phi(\vec G)$ $\vec G$
Aufgrund der Zulässigkeit hat einen Zyklus und daher einen SCC mit einer Kante darin. $\vec G$

Andrew Morgan
quelle

Schöne Beobachtung! Eine einfachere Möglichkeit, dies zu sehen (wie Sie sagen, "eliminieren Sie die graphentheoretische Terminologie"), besteht darin, zu beobachten, dass, wenn eine Zuordnung a F erfüllt, die Zuweisung a '(x) = 1-a (x) auch F erfüllt. Dies kann leicht durch Induktion auf die Anzahl der Variablen von F.

holf

Ich denke nicht, dass als gegeben eine Involution ist. Betrachten Sie beispielsweise das 4-Element-Diagramm mit den gerichteten Kanten . Dies ist eine zulässige Orientierung. Angenommen, sein erster Zyklus ist ; dann, nachdem dieser Zyklus umgekehrt wurde, entsteht ein neuer Zyklus, nämlich. . Wenn dieser Zyklus vor dem ursprünglichen bestellt wird, sind wir in Schwierigkeiten.

Φ

$\Phi$

0 \to 1 \to 2 \to 0 \to 3 \to 1

$0\to1\to2\to0\to3\to1$

0 \to 1 \to 2 \to 0

$0\to1\to2\to0$

0 \to 3 \to 1 \to 0

$0\to3\to1\to0$

Emil Jeřábek 3.0

@holf Deine Beobachtung ist auch falsch. Betrachten Sie den CNF mit den Klauseln , und . Dies wird durch die Zuordnung erfüllt , nicht jedoch durch .

x

$x$

\neg x \lor y \lor \neg z

$\neg x\lor y\lor\neg z$

\neg y \lor z

$\neg y\lor z$

(1, 1, 1)

$(1,1,1)$

(0, 0, 0)

$(0,0,0)$

Emil Jeřábek 3.0

Ich denke, die folgende Definition von könnte funktionieren. Sei die Menge der Eckpunkte mit der Eigenschaft, dass für jedes über einen (gerichteten) Pfad von aus erreichbar ist , über einen Pfad von aus erreichbar ist . (Als Modallogiker würde ich dies als die Vereinigung der letzten Cluster des transitiven reflexiven Schließens des gerichteten Graphen beschreiben. Ich weiß nicht, wie Graphentheoretiker es nennen würden.) Dann kehren Sie alle Kanten mit der Quelle um (daher auch das Ziel). in .

Φ

$\Phi$

M

$M$

x

$x$

y

$y$

x

$x$

x

$x$

y

$y$

M

$M$

Emil Jeřábek 3.0

@Emil: Ah ja, du hast recht. Wenn ich Ihren Vorschlag richtig verstehe, sagen Sie, brechen Sie die Ausrichtung in stark verbundene Komponenten und kehren Sie die Kanten innerhalb der Komponenten um. Ich denke das funktioniert. Ich werde meine Antwort entsprechend aktualisieren. Danke vielmals!!

Andrew Morgan

Ich bin mir nicht sicher, ob meine Idee verständlich ist, deshalb werde ich am Beispiel von Giorgio erklären:

$( x_1 \lor x_2 \lor x_3 ) \land ( \lnot x_1 \lor \lnot x_3 \lor x_4 ) \land ( \lnot x_4 \lor x_5 ) \land ( \lnot x_2 \lor \lnot x_5 \lor \lnot x_6 )$ .

Zuerst muss ich dies auf dem DNF-Formular ändern:

$( x_1 \land x_2 \land x_3 ) \lor ( \lnot x_1 \land \lnot x_3 \land x_4 ) \lor ( \lnot x_4 \land x_5 ) \lor ( \lnot x_2 \land \lnot x_5 \land \lnot x_6 )$ .

Dies sollte die gleiche Antwort geben. Und egal ob ich die Anzahl der Lösungen modulo 2 dafür berechne:

$( x_1 \land x_2 \land x_3 ) \lor ( \lnot x_1 \land \lnot x_3 \land x_4 ) \lor ( \lnot x_4 \land x_5 ) \lor ( \lnot x_2 \land \lnot x_5 \land \lnot x_6 )$ = 0

oder dafür:

$( x_1 \land x_2 \land x_3 ) \lor ( \lnot x_1 \land \lnot x_3 \land x_4 ) \lor ( \lnot x_4 \land x_5 ) \lor ( \lnot x_2 \land \lnot x_5 \land \lnot x_6 )$ = 1.

Also wähle ich die zweite. Ich habe Implikanten:

$i_0$ = $( x_1 \land x_2 \land x_3 )$

$i_1$ = $( \lnot x_1 \land \lnot x_3 \land x_4 )$

$i_2$ = $( \lnot x_4 \land x_5 )$

$i_3$ = $( \lnot x_2 \land \lnot x_5 \land \lnot x_6 )$

Jetzt baue ich ein Gleichungssystem:

${j_0}\oplus{j_1} = 1$

${j_0}\oplus{j_3} = 1$

${j_0}\oplus{j_1} = 1$

${j_2}\oplus{j_3} = 1$

${j_3} = 1$

Dieses System hat eine Lösung. 1 mod 2 = 1, also ist die Antwort 1. Aber kommt nur einmal vor. Wenn jede Variable zweimal vorkommt, kann die Antwort = 1? $x_6$

Maciej
quelle

Wenn mein Denken in Ordnung ist, lautet die Antwort "Nein". Natürlich gehe ich davon aus, dass die Variable einmal positiv und einmal negativ auftritt.

Maciej

Ich habe die Gleichung für vergessen : = 1. Aber Ergebnis, wenn das gleiche. Eine Lösung: = 1, = 0, = 1, = 0.

x_{4}

$x_4$

j_{1} \oplus j_{2}

${j_1}\oplus{j_2}$

j_{3}

$j_3$

j_{2}

$j_2$

j_{1}

$j_1$

j_{0}

$j_0$

Maciej

-1

Entschuldigung für die große Verzögerung. Bisher war das Problem wahrscheinlich gelöst. Wenn nicht, werde ich meinen Polynomalgorithmus zum Lösen von . Versuchen wir zunächst, die Anzahl der Lösungen Modulo 2 dieser Gleichung zu berechnen: . Wobei f und g logische Funktionen sind und X ein Vektor von Variablen ist. Der gemeinsame Teil tritt zweimal auf (einmal in f (X) und einmal in g (X)). In Modulo 2 ist der gemeinsame Teil also nicht wichtig. Wir können die Anzahl der Lösungen Modulo 2 von und die Anzahl der Lösungen Modulo 2 von berechnen und dann die Ergebnisse Modulo 2 summieren. Nehmen wir nun an, dass die Funktion in dieser Form dargestellt wird: $\oplus\text{Rtw-Opp-CNF}$ ${f(X)}\oplus{g(X)}$ $f(X) \wedge g(X)$ $f(X)$ $g(X)$

$i_0\oplus{i_1}\oplus{i_2}\oplus{...}\oplus{i_{n-1}}$ ,

Dabei ist ein Implikant (ich meine Variablen, die durch den AND-Operator verbunden sind; zum Beispiel: ). $i_j$ $x_0\wedge{x_1}\wedge{\neg{x_2}}$

Um die Anzahl der Lösungen dieser Funktion Modulo 2 zu berechnen, können wir einfach die Anzahl der Lösungen jedes Implikanten Modulo 2 berechnen und alle Ergebnisse Modulo 2 summieren. Wenn wir einen Vektor der Variablen X haben und im Implikanten nicht alle Variablen dieses Vektors vorhanden sind, dann wissen wir es Diese Anzahl von Lösungen Modulo 2 für diesen Implikanten ist 0, da es Lösungen gibt, wobei k die Anzahl der fehlenden Variablen ist. Wenn der Implikant alle Variablen hat, beträgt die Anzahl der Lösungen 1 (k = 0). Die Berechnung der Anzahl der Lösungen modulo 2 von ist daher einfach. Betrachten wir nun: $2^k$ $i_0\oplus{i_1}\oplus{i_2}\oplus{...}\oplus{i_{n-1}}$

$i_0\vee{i_1}\vee{i_2}\vee{...}\vee{i_{n-1}}$ .

Wir wissen, dass . Im Allgemeinen kann die ODER-Verknüpfung durch XOR jeder Teilmenge von Implikanten ersetzt werden, die durch den UND-Operator verbunden sind. Und das ist ein wichtiger Schritt: Wir interessieren uns nur für die Teilmengen, die: $a\vee{b} = a\oplus{b}\oplus({a\wedge{b}})$

1) hat alle Variablen,

2) Jede Variable kommt genau eins vor (wenn die Variable zweimal vorkommt, haben wir positiv und negativ in einem Implikanten, also ergibt dies 0).

Nehmen wir an, wir haben positives im impliziten und negatives im impliziten . Dann können wir schreiben und gleichsetzen: $x_0$ $i_0$ $x_0$ $i_1$

${j_0}\oplus{j_1} = 1$ .

In dieser Gleichung entsprechen die Variablen und Implikanten und . Ich meine, wenn zum Beispiel der implizite in einer Teilmenge auftritt, dann ist = 1. Andernfalls ist = 0. Wenn wir dies für alle Variablen machen, erhalten wir einen Satz von XOR-Gleichungen und müssen die Anzahl der Lösungen dieser Menge berechnen. Dieses Problem ist einfach. Anzahl der Lösungen, wenn immer , wenn l ein zu findender Wert ist. Das ist alles. Ich weiß, dass dies kein formaler Beweis ist, aber ich hoffe, dass es verständlich ist. ${j_0}$ ${j_1}$ $i_0$ $i_1$ $i_0$ $j_0$ $j_0$ $2^l$

Maciej
quelle

Hmmm .... Gibt es einen Fall, in dem = 1 ist?

\oplus Rtw-Opp-CNF

$\oplus\text{Rtw-Opp-CNF}$

Maciej

@AndrewMorgan Aber eine Formel mit einer eindeutigen Klausel, die alle Variablen genau einmal enthält, wäre keine Formel, die zweimal gelesen wird. Die Einschränkung ist genau zweimal, höchstens zweimal.

Giorgio Camerani

@AndrewMorgan Die folgende Formel (die nicht zweimal gelesen wird, weil nur einmal vorkommt) enthält eine ungerade Anzahl zufriedenstellender Zuweisungen: . Alle Variablen einer solchen Formel mit Ausnahme von den entgegengesetzten Einschränkungen beim zweimaligen Lesen, und die Anzahl der erfüllenden Zuweisungen ist ungerade, obwohl die Formel nicht "eine eindeutige Klausel enthält, die alle Variablen genau einmal enthält" .

x_{6}

$x_6$

(x_{1} \lor x_{2} \lor x_{3}) \land (\neg x_{1} \lor \neg x_{3} \lor x_{4}) \land (\neg x_{4} \lor x_{5}) \land (\neg x_{2} \lor \neg x_{5} \lor \neg x_{6})

$( x_1 \lor x_2 \lor x_3 ) \land ( \lnot x_1 \lor \lnot x_3 \lor x_4 ) \land ( \lnot x_4 \lor x_5 ) \land ( \lnot x_2 \lor \lnot x_5 \lor \lnot x_6 )$

x_{6}

$x_6$

Giorgio Camerani

@GiorgioCamerani Ich meinte, dass unter allen Klauseln, die alle Variablen enthalten, eine eindeutige Klausel in der Eingabeformel vorhanden ist. dh in einer Formel wie gibt es eine eindeutige Klausel, in der alle Variablen einmal vorhanden sind, während in oder gibt es nicht. Ich wollte das Vorhandensein anderer Klauseln in der Eingabe nicht ausschließen. Aber auf jeden Fall glaube ich, dass ich Maciejs Antwort falsch verstanden habe, also habe ich meinen vorherigen Kommentar gelöscht.

(x_{1} \lor x_{2}) \land (\bar{x_{1}}) \land (\bar{x_{2}})

$(x_1 \vee x_2) \wedge (\bar{x_1}) \wedge (\bar{x_2})$

(x_{1} \lor x_{2}) \land (\bar{x_{1}} \lor \bar{x_{2}})

$(x_1 \vee x_2) \wedge (\bar{x_1} \vee \bar{x_2})$

(x_{1}) \land (\bar{x_{1}}) \land (x_{2}) \land (\bar{x_{2}})

$(x_1) \wedge (\overline{x_1}) \wedge (x_2) \wedge (\overline{x_2})$

Andrew Morgan

@ AndrewMorgan OK, jetzt verstehe ich. Bedenken Sie jedoch, dass auch in der von Ihnen gemeinten Fallfamilie die Anzahl der zufriedenstellenden Aufgaben gerade zu bleiben scheint. Die Frage, die Maciej in seinem Kommentar gestellt hat, stellt sich als herausfordernd heraus.

Giorgio Camerani