A Cooke-Levin- tétel (szintén csak Cooke-tétel ) kimondja, hogy a CNF -ben ( SAT ) egy Boole-képlet kielégítési problémája NP-teljes .
Ennek a tételnek a bizonyítása, amelyet Stephen Cook 1971 -ben végzett alapvető munkájában, az NP-teljes problémák elméletének egyik első fontos eredménye volt. Ezzel párhuzamosan ezt a tételt Leonid Levin szovjet matematikus is bebizonyította [1] .
A Cook-tétel bizonyítása során az NP osztály minden egyes problémája kifejezetten SAT-ra redukálódik. S. Cook a tulajdonságfelismerési problémák NP osztályát a következőképpen definiálta. Egy feladat akkor tartozik az NP osztályba, ha:
Ez az osztály, amint azt R. Karp később bemutatta, a problémák egy másik széles osztályát is tartalmazza, amelyeket Karp NP-complete problémáknak vagy NPC-knek neveznek, és ezen az osztályon belül egymásra redukálva.
A Cook-féle eredmények megjelenése után az NP-teljesség számos egyéb problémára is bebizonyosodott. Ilyenkor leggyakrabban egy adott feladat NP-teljességének bizonyítására a SAT-probléma adott feladatra való polinomiális redukcióját adják meg, esetleg több lépésben, azaz több köztes feladat felhasználásával.