Informatik

Was besagt der Satz von Cook-Levin?

Das Erfüllbarkeitsproblem SAT ist NP-vollständig.

Beweisidee: Jede polynomielle nichtdeterministische Berechnung lässt sich als aussagenlogische Formel kodieren.

comp NDTM-Berechnung Zeit p(n) tab Tableau Zeit x Band comp->tab phi Boolesche Formel Konsistenzbedingungen tab->phi sat SAT-Instanz phi->sat