Satz 3SAT ist NP-vollständig
SAT 3SAT ist NP-vollständig
Einfache Sprache
Def. SAT 3SAT ist NP-vollständig
3SAT ist NP-vollständig.
Beweisidee: Aus Satz 3SAT ist in NP wissen wir, dass $\mathrm{3SAT}\in\mathbf{NP}$. Daher müssen wir nach der Definition von NP-Vollständigkeit nur noch zeigen das jede Sprache in $\mathbf{NP}$ polynomial reduzierbar auf $\mathrm{3SAT}$ ist. Dazu benutzen wir den Satz NP-vollständig durch Reduktion von NP-vollständig um von der NP-Vollständigkeit von SAT auf die NP-Vollständigkeit von $\mathrm{3SAT}$ zu schließen.
Klassischer Beweis
Beweis: Wir ändern die Reduktion im Satz von Cook und Levin so, dass nur Formeln in Konjunktive Normalform mit 3 Literalen pro Klausel entstehen. Dazu gehen wir jetzt die einzelnen Bestandteile der Formel durch:
Die Formel $\phi_\mathrm{cell}$ is schon in KNF. $\phi_\mathrm{start}$ ist ein $\mathrm{AND}$ von variablen. Betrachtet man jede Variable als eine Klausel der Größe 1, dann ist es in KNF. $\phi_\mathrm{accept}$ ist eine $\mathrm{OR}$ von variablen und damit eine einzelne Klausel.
$\phi_\mathrm{move}$ ist die einzige Formel die nicht in KNF ist. Sie ist ein $\mathrm{AND}$ von $\mathrm{ORs}$ von $\mathrm{ANDs}$. Nach dem Distributivgesetz können wir ein $\mathrm{OR}$ von $\mathrm{ANDs}$ durch ein $\mathrm{AND}$ von $\mathrm{ORs}$ ersetzen. Diese Operation erhöht die Größe der Formel signifikant. Aber betrachtet man die absolute Vergrößerung der Formel $\phi_\mathrm{move}$ ist diese Konstant in der Abhängigkeit von $N$. Alle viel Formeln zusammen sind somit in KNF. Jetzt muss nur noch gezeigt werden wie wir alle Klauseln in Klauseln der “Größe 3” transformieren. Dafür gibt es drei Fälle: Hat die Klausel schon genau 3 Literale, muss nichts gemacht werden. Hat die Klausel weniger als 3 Literale, dupliziere eines der Literale in der Klausel 1 bzw. 2 mal. Hat die Klausel mehr als 3 Literale, wird diese in mehrere Klauseln geteilt, die jeweils durch zusätzliche Variablen “verbunden” sind. Funktion der zusätzlichen Variablen ist die Erfüllbarkeit zu erhalten. So wird eine Klausel der Größe $l$,
$$(a_1\lor a_2\lor\ldots\lor a_l)\;,$$wie folgt durch $l-2$ Klauseln ersetzt, wobei $z_i$ mit $i\in[1,l-3]$ die zusätzlichen Variablen sind,
$$(a_1\lor a_2\lor z_1)\land(\overline{z_1}\lor a_3\lor z_2)\land(\overline{z_2}\lor a_4\lor z_3)\land\ldots\land(\overline{z_{l-3}}\lor a_{l-1}\lor a_l)$$Die neue Formel ist erfüllbar gdw. die Original Formel erfüllbar ist.
Beweis über Schaltungskomplexität
- Beweis über Reduktion auf Problem Schaltungs-SAT das nach Satz CIRCUIT-SAT ist NP-vollständig