Satz von Cook und Levin

Der Satz von Cook und Levin ist ein fundamentales Theorem der Komplexitätstheorie. Er besagt:
SAT ist NP-vollständig.
Dies war der erste Beweis eines NP-vollständigen Problem und ermöglichte Beweise für andere Probleme durch Reduktion von SAT.