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.