Jabarkan Ide pembuktian: dari Teorema Cook

Untuk setiap A adalah NP, dengan input w, menghasilkan sebuah formula boolean φ yang mensimulasikan mesin turing menghasilkan A pada input w.

Lakukan pengecekan apakah formula boolean yang dihasilkan satisfiable.

Ide tersebut dapat diilustrasikan pada gambar dibawah ini