Einzigartige 1-in-3-Sat

Question

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

Ich kenne den Wert jedes Bits der eindeutigen Zuweisung, da es aus einer binären Multiplikationsschaltung hergestellt wurde, 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. Die einzige Möglichkeit, die Formel zu erfüllen, besteht darin, die Werte von A und B in die richtige Reihenfolge in die Eingangsbits zu bringen.

Die Anzahl der echten Literalen in jeder Klausel ist entweder 1, 2 oder 3. Weil ich den Wert jedes Bits kenne, kann ich sagen, welche Literale in jeder Klausel wahr sind, und zählen Sie sie. Ich weiß zum Beispiel, welche Klauseln mit genau 1 Literal zufrieden sind. Und dass das Literal logisch ein Teil der einzigartigen Lösung ist.

Meine Frage ist einfach: Wenn ich alle Klauseln mit mehr als einem echten Literal enthalte, ist der Auftrag zwangsläufig noch einzigartig?

Mit anderen Worten, wenn ich einen aufklärungslosen Auflösung (wahrscheinlich exponentiell lang) aufschreiben wollte, um zu demonstrieren, dass die Lösung eindeutig ist (ein anderes Lösungsproblem, in Co-NP), kann ich es mit nur die Klauseln mit 1 schreiben echtes wörtliches?

Intuitiv glaube ich, aber ich kann meinen Standpunkt nicht verteidigen, selbst wenn ich an das 2sat-Äquivalent nachgedacht.

Answer 1

Betrachten Sie die folgende CNF: $$ (a \ lor \ lnot b) \ land (\ lnot a \ lor b) \ land (a \ lor b). $$ Es hat einen einzigartigen, zufriedenstellenden Auftrag, $ a= b=top $ , das die letzte Klausel zweimal erfüllt.Wenn Sie jedoch die letzte Klausel entfernen, erhalten Sie eine weitere erfüllende Aufgabe, $ A= B=Bot $ .