Jelaskan Pembuktian: dari Teorema Cook

N	: mesin turing NP yang menentukan A

N menentukan w∈anggota A dalan nk langkah untuk constanta k

Sebuah variable dapat dinyatakan dalam Xi,j,s

Xi,j,s: true jika cell [i,j] bernilai s; selain itu bernilai false

cell[i,j]: cell dengan lokasi baris ke-i dan kolom ke -j

Suatu Tableau tanpa aturan tertentu dapat berisi konfigurasi yang invalid, misal: cell berisi multiple symbols, tidak dimulai dengan input w dan state q0, konfigurasi neighbour tidak berkorespondensi dengan aturan transisi, dan sebagainya. Sehingga harus dihasilkan formula Boolean yang memaksa tableau agar valid dan menghasilkan result pada accet state.

Sebuah cell dapat berisi tepat 1 symbol di antara sebuah state, sebuah alphabet tape, dan sebuah #. (φ cell)

Konfigurasi pertama harus berhubungan dengan input w dan state awal q. (φ start)

Sebuah konfigurasi diturunkan dari konfigurasi sebelumnya sesuai dengan aturan transisi pada mesin turing. (φmove)

Harus terdapat sebuah cell berisi accept state. (φaccept)