DAA - Teorema Cook
Stephen Cook mempresentasikan empat teorema dalam makalahnya “Prosedur Pembuktian Teorema Kompleksitas”. Teorema ini dinyatakan di bawah ini. Kami memahami bahwa banyak istilah yang tidak diketahui digunakan dalam bab ini, tetapi kami tidak memiliki ruang lingkup untuk membahas semuanya secara rinci.
Berikut adalah empat teorema oleh Stephen Cook -
Teorema-1
Jika satu set S string diterima oleh beberapa mesin Turing non-deterministik dalam waktu polinomial, lalu S adalah P-reducible menjadi {DNF tautologies}.
Teorema-2
Kumpulan berikut dapat direduksi-P satu sama lain secara berpasangan (dan karenanya masing-masing memiliki tingkat kesulitan polinom yang sama): {tautologies}, {DNF tautologies}, D3, {sub-graph pairs}.
Teorema-3
Untuk apapun TQ(k) tipe Q, $ \ mathbf {\ frac {T_ {Q} (k)} {\ frac {\ sqrt {k}} {(log \: k) ^ 2}}} $ tidak dibatasi
Ada sebuah TQ(k) tipe Q sedemikian rupa sehingga $ T_ {Q} (k) \ leqslant 2 ^ {k (log \: k) ^ 2} $
Teorema-4
Jika himpunan S string diterima oleh mesin non-deterministik dalam waktu T(n) = 2n, dan jika TQ(k) adalah fungsi tipe yang jujur (dapat dihitung secara real-time) Q, lalu ada konstanta K, jadi S dapat dikenali oleh mesin deterministik dalam waktu TQ(K8n).
Pertama, ia menekankan pentingnya reduksi waktu polinomial. Ini berarti bahwa jika kita memiliki pengurangan waktu polinomial dari satu masalah ke masalah lainnya, ini memastikan bahwa algoritma waktu polinomial dari masalah kedua dapat diubah menjadi algoritma waktu polinomial yang sesuai untuk masalah pertama.
Kedua, ia memusatkan perhatian pada kelas NP dari masalah keputusan yang dapat diselesaikan dalam waktu polinomial oleh komputer non-deterministik. Sebagian besar masalah yang sulit diselesaikan milik kelas ini, NP.
Ketiga, ia membuktikan bahwa satu masalah tertentu di NP memiliki properti bahwa setiap masalah lain di NP dapat direduksi secara polinomial menjadi masalah tersebut. Jika masalah kepuasan dapat diselesaikan dengan algoritma waktu polinom, maka setiap masalah dalam NP juga dapat diselesaikan dalam waktu polinomial. Jika ada masalah di NP yang sulit dipecahkan, maka masalah kepuasan harus sulit diselesaikan. Jadi, masalah kepuasan adalah masalah tersulit di NP.
Keempat, Cook menyarankan bahwa masalah lain di NP mungkin berbagi dengan masalah kepuasan properti ini sebagai anggota NP yang paling sulit.