Einzigartiger 3sat zum einzigartigen 1-in-3sat

Question

Angenommen, ich habe eine CNF-Formel mit Klauseln der Größe 2 und 3. Es hat eine einzigartige zufriedenstellende Aufgabe.

Es wurde aus einer binären Multiplikationsschaltung hergestellt, in der ich zwei Primingszahlen A und B so multipliziert habe, dass A * B= S, wobei S eine SemiPrime-Nummer ist. Ich fügte die Bedingungen hinzu, die ein!= 1, B!= 1 und A <= B, dann hinzugefügt, der Wert von s in die Formel hinzugefügt, um sicherzustellen, dass die Zuordnung eindeutig ist. Der einzige Weg, um die Formel zu erfüllen, besteht darin, die Werte der Primaten A und B in die richtige Reihenfolge in die Eingangsbits zu setzen.

In 1-in-3sat zwingen wir, dass genau 1 Literal in jedem Triplett und zwei anderen falsch sein sollte. Wenn genau 2 Literale wahr sind, können wir alle Efresalien in der Klausel umdrehen, um eine äquivalente 1-in-3sat-Klausel zu erhalten (mit anderen Worten 2-in-3sat ist das gleiche Problem).

grundlegende Beobachtung: Während eine regelmäßige oder ein Klausel 1 die Möglichkeit von 8 eliminiert, eliminiert eine 1-in-3-Klausel 5 Möglichkeiten von 8.

3sat kann auf 1-in-3 sanisiert werden, so dass, wenn die 3sat-Formel erfüllt ist, also die reduzierte Formel.

Die Reduzierungen scheinen jedoch nicht die Anzahl der Zuweisungen zu erhalten, indem neue Variablen eingeführt werden, ohne ihren Wert zu erzwingen.

kann eindeutig 3sat auf eindeutiges 1-in-3sat reduziert werden ...

.
1. ohne die korrekte Aufgabe zu kennen?
2. wenn nicht, während Sie die korrekte Aufgabe kennen?

Answer 1

ja, eine 3-sat-Formel-Formel $ \ phi $ kann in eine 1-in-3-Sat-Formel umgewandelt werden $ \ phi '$ Während der Anzahl der erfüllenden Aufgaben erhalten bleibt. Um Mehrheiten zu vermeiden, verwende ich " $ \ Vee $ " zwischen Literalen einer 3-Sat-Klausel und Kommas zwischen Literalen einer 1-in-3-Sat-Klausel. < / p>

---

Lassen Sie mich vorläufig dazu zeigen, dass es zwei Literalkenntnisse $ A $ und $ B $ , wir können Simulieren Sie eine neue Art von Klausel $ (x= a \ wedge b) $ , die den Wert einer neuen Variablen $ x zwingt $ , um $ A \ wedge B $ nur 1-in-3-SAT-Einschränkungen, ohne neue Lösung einzuführen.

Betrachten Sie die Cluases: $$ (\ Overline {b}, c, x) \ wedge (a, c, d) \ wedge (\ Overline {a}, e, x) \ wedge (b, e, f) $$

wenn $ a=top $ und $ b=top $ , dann die 2. und 4. Klauseln sorgt dafür, dass $ C= D= E= f=bot $ . Die 1. und 3. Klauseln stellt dann sicher, dass $ x=top $ .

wenn $ a=top $ und $ b=bot $ , dann die 2. Die Klausel stellt sicher, dass $ C= D=Bot $ . Die erste Klausel stellt dann sicher, dass $ x=bot $ . Die dritte Klausel stellt sicher, dass $ e=top $ , und die 4. Klausel impliziert $ f=bot $ .

Der Fall $ a=Bot $ und $ B=Top $ ist symmetrisch.

wenn $ A=Bot $ und $ B=Bot $ , dann die 1. und 3. Klauseln implizieren $ C= E= x=Bot $ . Die 2. und 4. Klauseln sorgen für $ d= f=top $ .

---

Ich bin jetzt bereit, eine Formel-Klasse $ \ phi $ von 3sat in eine Formel $ \ phi '$ < / span> von 1-in-3 saß. Berücksichtigen Sie jetzt eine Klausel $ (a \ vee b \ vee c) $ von $ \ phi $ . Dies kann in die folgenden äquivalenten 1-in-3-Sat-Klauseln umgewandelt werden:

.

• Fügen Sie eine neue Variable hinzu $ x $ Das ist echte IFF $ A $ ist falsch und $ B $ ist wahr. Dies wird von der Klausel $ (x=Overline {A} \ wedge b) $ codiert.

• Fügen Sie eine neue Variable hinzu $ y $ Das ist echte IFF $ A $ ist falsch , $ B $ ist falsch, und $ C $ ist wahr. Wir benötigen eine zusätzliche Variable $ Z $ . Die Klausel $ (Z=Overline {A} \ wedge \ overline {b}) $ stellt sicher, dass $ z $ < / span> ist true, wenn und nur wenn $ A $ FALSE und $ B $ ist falsch ist. Dann kann der Wert von $ y $ durch die Klausel $ (y= z \ wedge c) $ .

• Wenn $ (a \ vee b \ vee c) $ true ist, dann ist mindestens einer von $ Eine $ , $ B $ oder $ C $ ist wahr. Dies bedeutet, dass genau einer der Math-Container "> $ A $ , $ x $ , und $ y $ ist wahr. Wenn der Converse, wenn $ (a \ vee b \ vee c) $ FALSE ist, ist dann auf allen $ A $ , $ x $ , und $ y $ sind falsch. Dies zeigt, dass $ (a \ vee b \ vee c) $ erfüllt ist, wenn und nur wenn $ (A, X, y $ ) ist erfüllt.

Wir haben dann eine äquivalente 1-in-3-Sat-Formel $ \ phi '$ aufgebaut, die einen Superset der Variablen der ursprünglichen 3 SAT-Formel $ \ phi $ . Eine Wahrheitsaufgabe zu den Variablen von $ \ phi '$ erfüllt $ \ phi' $ , wenn und nur wenn Die Zuordnung, die auf die Variablen von $ \ phi $ beschränkt ist, erfüllt $ \ phi $ . Wenn also eine neue Lösung für $ \ phi '$ eingeführt wird, muss er an den neu hinzugefügten Variablen $ x sein $

n>, $ y $ und $ Z $ (ein Set für jede Klausel).Die Werte dieser Variablen werden jedoch vollständig durch die Werte der Variablen von $ \ phi $ bestimmt.

Answer 2

Eine solche Verringerung ist in Anhang B von Régis Barbanchon, auf eindeutiger graph 3-Färblichkeit und sparsame Reduzierungen in der Ebene .Barbanchon schreibt es zur vorherigen Arbeit ([9] in der Bibliographie).An anderer Stelle habe ich eine Zuschreibung an Schaefers gefeiertes Papier gesehen, in dem er seinen berühmten Dichotomie-Theorem erweist, unter anderem eine Reduktion von 3sat bis 1-in-3sat, der angeblich parsimonisch ist (ich habe nicht geprüft).