Direkt zum Inhalt

Lexikon der Mathematik: Cook, Satz von

die Aussage, daß das Erfüllbarkeitsproblem für die Konjunktion von Klauseln, also Disjunktionen von Literalen, NP-vollständig ist.

Mit seinem Satz ist es Cook erstmals gelungen, die NP-Vollständigkeit eines Problems zu beweisen. Dazu war es nötig, alle Probleme in der Komplexitätsklasse NP polynomiell auf das oben beschriebene Erfüllbarkeitsproblem zu reduzieren.

Cook hat zulässige Rechenwege nichtdeterministischer Turing-Maschinen durch Konjunktionen von Klauseln codiert. Spätere NP-Vollständigkeits-beweise für andere Probleme konnten die Transitivität polynomieller Reduktionen ausnutzen und sich auf den Satz von Cook stützen.

Lesermeinung

Wenn Sie inhaltliche Anmerkungen zu diesem Artikel haben, können Sie die Redaktion per E-Mail informieren. Wir lesen Ihre Zuschrift, bitten jedoch um Verständnis, dass wir nicht jede beantworten können.

  • Die Autoren
- Prof. Dr. Guido Walz

Partnervideos