Satz von Cook und Levin

Einfache Sprache

Der

Def. Satz von Cook und Levin

SAT ist NP-vollständig

Idee: $\mathrm{SAT}\in\mathbf{NP}$ ist einfach zu zeigen. Der schwere Teil ist zu zeigen das jede Sprache in NP polynomial reduzierbar auf SAT ist. Die Idee der Reduktion ist: die Reduktion bekommt für eine Sprache $A\in\mathbf{NP}$ eine Eingabe $w$. Daraus produziert sie eine Aussagenlogischen Formel $\phi$ die $A$ auf der Eingabe $w$ simuliert. Falls $A$ akzeptiert, hat $\phi$ eine erfüllende Belegung, die der akzeptierenden Berechnung entspricht.. Falls $A$ nicht $akzeptiert, erfüllt keine Belegung $\phi$. Also ist $w\in A\iff \phi\text{ ist erfüllbar}$

Beweis: