Satz von Cook

Bedeutung: SAT ist das "erste" NP-vollständige Problem. Wenn wir SAT effizient (in P) lösen könnten, könnten wir alle Probleme in NP effizient lösen.

Beweis-Idee (Skizze)

1. SAT $\in$ NP: Gegeben eine Belegung, können wir in Polynomialzeit prüfen, ob die Formel wahr ist.
2. NP-Härte: Wir müssen zeigen, dass jedes Problem $L\in NP$ auf SAT reduzierbar ist.
   • Da $L\in NP$, gibt es eine nicht-deterministische Turingmaschine (NTM) $M$, die $L$ in Zeit $p(n)$ entscheidet.
   • Wir konstruieren für jede Eingabe $w$ eine aussagenlogische Formel ${\phi }_w$, die "den Lauf der Maschine $M$ auf $w$" simuliert.
   • ${\phi }_w$ ist erfüllbar $⟺$ es gibt einen akzeptierenden Lauf von $M$ auf $w$.