Jabarkan Jika φ satisfiable, maka dari Teorema Cook

Karena A dapat direduksi menjadi problem SAT dengan input w, dan SAT adalah problem NP, maka terbukti bahwa SAT adalah NP-complete.