Überprüfung einer Subtilität von Karps ursprünglichem Beweis, dass SAT eine Polynomzeitreduktion auf 3SAT aufweist

Kurz gesagt, meine Frage lautet: Ist Karps ursprünglicher Beweis, der SAT auf 3SAT reduziert, unnötig aufwändig? Die Einzelheiten sind wie folgt.

In seiner Arbeit Reducibility Among Combinatorial Problems aus dem Jahr 1972 bewies Karp, dass sich SAT auf 3SAT reduziert, indem er Folgendes feststellte:

Ersetzen einer Klausel , wobei die Literalen sind und , die von $\sigma_1 \cup \sigma_2 \cup \ldots \cup \sigma_m$ $\sigma_i$ $m>3$ wobei eine neue Variable ist. Wiederholen Sie diese Umwandlung, bis keine Klausel mehr als drei Literale enthält.
$(σ_{1} \cup σ_{2} \cup u_{1}) (σ_{3} \cup \dots \cup σ_{m} \cup {\bar{u}}_{1}) ({\bar{σ}}_{3} \cup u_{1}) \dots ({\bar{σ}}_{m} \cup u_{1}),$ $(\sigma_1 \cup \sigma_2 \cup u_1) (\sigma_3 \cup \ldots \cup \sigma_m \cup \bar{u}_1) (\bar{\sigma}_3 \cup u_1) \ldots (\bar{\sigma}_m \cup u_1),$ $u_1$

Es scheint mir, dass die letzten Klauseln (dh die Klauseln, die zwei Literale enthalten) hier unnötig sind. Die Konstruktion ist also wie geschrieben korrekt, aber aufwändiger als nötig. Ohne die 2-Literal-Klauseln erhalten wir die Konstruktion, die normalerweise in Lehrbüchern für Studenten angegeben ist. Ist das richtig oder fehlt mir etwas Offensichtliches? Ich bin mir sehr unsicher, ob etwas, das Karp getan hat, eleganter ausgedrückt werden könnte. $m-2$

cc.complexity-theory sat reductions John MacCormick
quelle

Antworten:

$(\sigma_1\cup\sigma_2\cup u_1)(\sigma_3\cup\ldots\cup\sigma_m\cup\bar{u}_1)$ $\sigma_i$ $u_1$ $\sigma_i$ $u_1$ $\bar{u}_1$

$u_1$ $\sigma_3\cup\ldots\cup\sigma_m$

Klaus Draeger
quelle

Danke für die hilfreiche Antwort. Um mein Verständnis zu erweitern und zu überprüfen, besteht eine andere Möglichkeit, dies zu erklären, darin, dass die zusätzlichen Klauseln sicherstellen, dass dies eine Reduzierung von #SAT auf # 3SAT darstellt (da sie die Anzahl der Lösungen und nicht nur die Existenz von Lösungen bewahren).

John MacCormick