Der Satz von Cook besagt, daß das Erfüllbarkeitsproblem (vgl. Kapitel 34) NP-vollständig ist. Er benutzt dabei eine generische Transformation, die jedes Problem in NP (vgl. Kapitel 41) in Polynomialzeit auf das Erfüllbarkeitsproblem abbildet. Die Grundbestandteile dieser Transformation sind lediglich aus mehreren Systemen von Klauseln zusammengesetzt, welche die Arbeitsweise einer Turing-Maschine in logischer Form ausdrücken. Für jedes Problem in NP ist die betreffende Turing-Maschine die nichtdeterministische Turing-Maschine, die das Problem in Polynomialzeit löst. Auf jeden Fall kann man die generische Transformation weitgehend als einen in logische Form gebrachten Ausdruck betrachten, der für alles gilt, was eine Turing-Maschine durchführen kann (oder nicht kann) (Abbildung 45.1).