Teorema Cook

Setiap problem NP dapat direduksi menjadi SAT dalam waktu polinomial
dapat dinyatakan dalam bentuk sebagai berikut : pict1
Akan diperlihatkan bahwa untuk setiap A ∈ NP dengan input w, sangat dimungkinkan untuk menghasilkan sebuah formula Boolean yag satisfiable jika w anggota A.
Ide pembuktian :