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.
Schreiben Sie uns!