Teorema Cook
Langkah - langkah pembuktian:
SAT adalah NP
SAT adalah NP karena masukan dari nilai Boolean ke variabel boolean memenuhi satisfiabliity dari suatu ekspresi yang dapat diverifikasikan dalam waktu polinomial oleh sebuah mesin turing deterministik.
contoh : E = (X V ¬X V X) Ʌ (X V X V ¬X) Ʌ (X V X) Ʌ (X)
dengan memberikan assignment pada variabel X, X, X. SAT adalah suatu ekspresi dalam bentuk CNF dan satisfiable jika menghasilkan nilai True.
Misal diberikan nilai :
X =T , X = T, X = T, maka ekspresi akan bernilai True. Untuk mengecek suatu problem SAT dengan memberikan nilai pada variabel, dapat diselesaikan dalam waktu polinomial, sehingga SAT adalah NP.