Teorema Cooke-Levin (de asemenea doar teorema lui Cooke ) afirmă că problema de satisfacție pentru o formulă booleană în CNF ( SAT ) este NP-complet .
Dovada acestei teoreme, obținută de Stephen Cook în lucrarea sa fundamentală în 1971 , a fost unul dintre primele rezultate importante ale teoriei problemelor NP-complete. În mod independent în același timp, această teoremă a fost demonstrată de matematicianul sovietic Leonid Levin [1] .
În demonstrarea teoremei lui Cook, fiecare problemă din clasa NP este redusă explicit la SAT. S. Cook a definit clasa NP a problemelor de recunoaștere a proprietăților după cum urmează. O sarcină aparține clasei NP dacă:
Această clasă, după cum a arătat R. Karp mai târziu, conține, la rândul său, o altă clasă largă de probleme, numită de Karp probleme NP-complete , sau NPC-uri, reduse una la alta în cadrul acestei clase.
După apariția rezultatelor lui Cook, NP-completitudinea a fost dovedită pentru multe alte probleme. În acest caz, de cele mai multe ori, pentru a demonstra NP-completitudinea unei anumite probleme, se dă o reducere polinomială a problemei SAT la problema dată, eventual în mai multe etape, adică folosind mai multe probleme intermediare.