Umwandlung zwischen k-SAT und XOR-SAT

8

Laut dem XOR Satisfiability Solver-Modul für die DPLL-Integration von Tero Laitinen benötigen wir CNF-Klauseln, um eine Literal-XOR-SAT-Klausel zu konvertieren , wenn wir die Anzahl der Literale nicht erhöhen möchten. Ich verstehe also, dass der Rechenaufwand für die Umwandlung eines XOR-SAT-Ausdrucks in einen streng CNF -SAT exponentiell ist.2n1nk

Meine Frage: Was sind die Rechenkosten, wenn ich den Prozess umkehren möchte? Was sind die Berechnungskosten für die Umwandlung eines CNF -SAT-Ausdrucks in einen XOR-SAT-Ausdruck? Ich gehe davon aus, dass in diesem Fall nur die SAT-Ausdrücke mit äquivalenten XOR-SAT-Ausdrücken berücksichtigt werden.kk

Omar Shehab
quelle
5
Ist es nicht im schlimmsten Fall eindeutig unmöglich? Einige CNF-Formeln sind nicht affin, daher können sie nicht als Konjunktion von XOR-Klauseln dargestellt werden.
Tsuyoshi Ito
1
Insbesondere hat keine äquivalente XOR-SAT-Formel. xy
Huck Bennett
@ TsuyoshiIto, stimmte zu. Ich denke, ich hätte ein Versprechen annehmen sollen, dass die -SAT-Ausdrücke äquivalente XOR-SAT-Ausdrücke haben. Aktualisieren der Frage. k
Omar Shehab
@ HuckBennett, ich habe ein Versprechen in die Frage aufgenommen.
Omar Shehab
1
Ich sehe, das macht das Problem interessant!
Tsuyoshi Ito

Antworten:

6

Wenn alle XOR-Beziehungen zwischen Variablen in CNF-Formeln in Polynomzeit erfasst werden könnten, würde dies die Lösung von UNAMBIGUOUS-SAT in Polynomzeit ermöglichen. Nach dem Valiant-Vazirani-Theorem würde dieses Ergebnis implizieren, dass NP = RP ist.

Um UNAMBIGUOUS-SAT zu lösen, denken Sie daran, dass impliziert . Suchen Sie die XOR-Beziehung zwischen jedem Variablenpaar und teilen Sie die Variablen anhand der Ergebnisse in zwei Gruppen äquivalenter Variablen auf. Sobald dies erledigt ist, sind nur zwei Testzuweisungen erforderlich, um die Erfüllbarkeit zu bestimmen.abab

In dem begrenzten Fall der Wiederherstellung von XOR-Beziehungen, die auf die übliche Weise codiert sind, d. H.

abc

zu

¬abca¬bcab¬c¬a¬b¬c

Dies kann in Polynomzeit erfolgen, indem die Klauseln sortiert werden, gefolgt von einem linearen Zeitscan.

Kyle Jones
quelle
Vielen Dank. Ich würde gerne wissen, wie komplex es ist, einen CNF-Ausdruck in einen XOR-SAT-Ausdruck umzuwandeln. Ich gehe davon aus, dass wir diejenigen CNF-Ausdrücke berücksichtigen, für die es äquivalente XOR-SAT-Ausdrücke gibt.
Omar Shehab
Können wir sagen, dass der Davis-Putnam-Logemann-Loveland-Algorithmus das mit Abstand bekannteste Ergebnis dafür ist?
Omar Shehab
2
Es sei denn, NP = RP (ein wunderbares Ergebnis), um XOR-Beziehungen zu erraten, wird im allgemeinen Fall eine exponentielle Zeit benötigt. Dies ist unabhängig vom verwendeten SAT-Lösungsalgorithmus.
Kyle Jones
Nicht implizieren ? P=UPP=NP
Rus9384