Bleibt 1-in-3-SAT NP-hart, auch wenn jede Variable sowohl positiv als auch negativ auftritt?

Das Standardproblem 1-in-3-SAT (oder XSAT oder X3SAT) lautet:
Instanz : Eine CNF-Formel, bei der jede Klausel genau 3 Literale enthält.
Frage : Gibt es eine zufriedenstellende Zuweisungseinstellung, bei der genau 1 Literal pro Klausel wahr ist?

Das Problem ist NP-vollständig und bleibt schwierig, auch wenn keine Variable negiert auftritt. Ich frage mich, ob dieses Problem einfach wird oder schwierig bleibt, wenn jede Variable mindestens einmal positiv und mindestens einmal negativ auftreten muss .

Die übliche Reduktion von 3SAT, die zeigt, dass 1-in-3-SAT hart ist, ersetzt eine Klausel durch Klauseln , , wobei $(x\lor y \lor z)$ $(\lnot x \lor a \lor b)$ $(y\lor b\lor c)$ $(\lnot z \lor c \lor d)$ $a,b,c,d$ sind für jede Klausel frisch. Daher hilft diese Reduzierung nicht bei der Beantwortung meiner Frage. Ich hatte Probleme, ein Gadget zu entwickeln, das die Härte dieser Variante zeigt, denn wenn genau 1 Literal in einer Klausel wahr ist, sind nicht symmetrisch 2 Literale falsch. Wenn es sich als einfach herausstellt, könnte es sein, in Partitionen des Klauselsatzes zu denken, aber ich kann nicht sehen, wie.

cc.complexity-theory np-hardness sat Dominik Peters
quelle

Kann es auf 2 Sat reduziert werden?

Joshua Herman

Hinweis: für jede var

, fügen Klauseln

und, sagen wir,

X_{i}

$X_i$

(X_{i} \lor {\bar{X}}_{i} \lor W) \land (X_{i} \lor {\bar{X}}_{i} \lor Y) \land (X_{i} \lor {\bar{X}}_{i} \lor Z)

$(X_i\vee \overline X_i \vee W) \wedge (X_i\vee \overline X_i \vee Y)\wedge (X_i\vee \overline X_i \vee Z)$

(W \lor Y \lor \bar{Z})

$(W \vee Y \vee \overline Z)$

Neal Young

Ha, das Werk (natürlich auch das Hinzufügen

). Ich werde die Frage offen lassen, falls jemand sie ohne den etwas unbefriedigenden Trick

lösen kann .

(\bar{W} \lor Y \lor Z) \land (W \lor \bar{Y} \lor Z)

$(\overline W \lor Y\lor Z)\land(W\lor\overline Y \lor Z)$

X_{i} \lor {\bar{X}}_{i}

$X_i\lor\overline X_i$

Dominik Peters

Darf ich Sie ermutigen, eine vollständige Antwort auf Ihre eigene Frage zu schreiben, vielleicht basierend auf der Idee von Neal Young? (Übrigens bin ich mir nicht sicher, warum das "unbefriedigend" ist. Eine Reduzierung ist eine Reduzierung.)

Wenn Ihnen dieser Sonderfall wirklich am Herzen liegt, ist es vielleicht sinnvoll, Ihre Frage zu bearbeiten, um diese zusätzliche Einschränkung widerzuspiegeln?

Antworten:

In einem Kommentar zeigte OP Interesse an einer Reduzierung, die Instanzen mit 3 verschiedenen Variablen pro Klausel erzeugte. Hier ist ein einfacher Ansatz:

Die Reduzierung erfolgt von 1 zu 3 SAT mit 3 verschiedenen Variablen pro Klausel:

Fügen Sie zunächst alle Klauseln in die Eingabeformel als Klauseln in die Ausgabeformel ein.
Zweitens führen Sie drei neue Variablen $F_1$ , $F_2$ und $F_3$ und fügen Sie der Ausgabeformel die folgenden drei Klauseln hinzu: $(\neg F_1, F_2, F_3)$ , $(F_1, \neg F_2, F_3)$ , und $(F_1, F_2, \neg F_3)$ .
Führen Sie schließlich für jede Variable $x$ in der ursprünglichen Formel eine neue Variable $x'$ und fügen Sie der Ausgabeformel die folgenden zwei Klauseln hinzu: $(x, x', F_1)$ und $(\neg x, \neg x', F_1)$ .

Lassen Sie uns überprüfen, ob diese Reduzierung das tut, was wir wollen. Folgende Eigenschaften wollen wir:

Jede Klausel hat immer drei verschiedene Variablen.
Jede Variable kommt in einer Klausel positiv und in einer Klausel negativ vor.
Die Eingabeformel entspricht der Ausgabeformel.

Eigenschaft 1 ist trivial zu überprüfen. Die Eigenschaft 2 ist ebenfalls leicht zu überprüfen: Die Variablen $F_1$ , $F_2$ und $F_3$ treten jeweils positiv und negativ in den im zweiten Aufzählungspunkt hinzugefügten Klauseln auf, während jede andere Variable in der Formel sowohl positiv als auch negativ in den Klauseln vorkommt im dritten Aufzählungspunkt hinzugefügt.

Die Eigenschaft 3 ist weniger trivial, aber dennoch einfach. Sie können leicht argumentieren, dass die einzige Zuweisung für die Variablen $F_1$ , $F_2$ und $F_3$ , die jede Klausel ab dem zweiten Aufzählungspunkt erfüllt, darin besteht, alle drei $F_i$ s falsch zu machen. Unter der Annahme eines Wertes von false für $F_1$ sind die im dritten Aufzählungspunkt hinzugefügten Klauseln $(x, x', F_1)$ und $(\neg x, \neg x', F_1)$ genau dann erfüllt, wenn $x' = \neg x$ . Da es für $x'$ keine anderen Einschränkungen gibt, bedeutet dies, dass es immer möglich ist, eine zufriedenstellende Zuordnung für die Eingabeformel in eine zufriedenstellende Zuordnung für die Ausgabeformel zu erweitern: Setzen Sie einfach jedes $x'$ als Negation des entsprechenden $x$ und setzen Sie jedes $F_i$ zu falsch.

Mikhail Rudoy
quelle