Teorema Cook

Dalam teori kompleksitas komputasi, **Teorema Cook-levin**, dikenal juga sebagai **Teorema Cook**, adalah suatu teori kompleksitas yang dicetuskan oleh Stephen Cook pada Tahun 1970 pada seminar nya, dengan judul "The Complexity of Theorem Prooving Procedures". Paper ini memperkenalkan teori NP-completeness yang hingga sekarang menjadi pusat dari teori ilmu komputer.
Teori NP-Completeness ini menyediakan suatu cara untuk mengkategorikan persoalan komputasi yang sulit dengan batas waktu, yaitu jumlah maksimal langkah -langkah yang diperlukan untuk menyelesaikan suatu masalah. Pada paper nya, Cook memaparkan fakta bahwa cukup banyak permasalahan yang sulit untuk diselesaikan tetapi mudah untuk diverifikasi kebenarannya pada kelas P (dalam waktu polinomial).

Teorema Cook-Levin atau dikenal juga dengan teorema Cook menyatakan bahwa:
**''Problem satisfiability'' (SAT) adalah NP-complete**

Terdapat 2 cara dalam pembuktian untuk teorema ini yaitu:
# SAT adalah NP
# Setiap problem NP dapat direduksi menjadi SAT dalam waktu polinomial

Langkah - langkah pembuktian:
**SAT adalah NP**
SAT adalah NP karena masukan dari nilai Boolean ke variabel boolean memenuhi *satisfiablility* dari suatu ekspresi yang dapat diverifikasikan dalam waktu polinomial oleh sebuah mesin turing deterministik.
contoh: E = (X1 V ¬X1 V X2) Ʌ (X3 V X2 V ¬X1) Ʌ (X1 V X2) Ʌ (X3)
dengan memberikan assignment pada variabel X1, X2, X3. SAT adalah suatu ekspresi dalam bentuk CNF dan satisfiable jika menghasilkan nilai True.
Misal diberikan nilai:
X1 =T, X2 = T, X3 = T, maka ekspresi akan bernilai True. Untuk mengecek suatu problem SAT dengan memberikan nilai pada variabel, dapat diselesaikan dalam waktu polinomial, sehingga **SAT adalah NP.** 

**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:**
* Untuk setiap A adalah NP, dengan input w, menghasilkan sebuah formula boolean φ yang menyimulasikan mesin turing menghasilkan A pada input w.
* Lakukan pengecekan apakah formula boolean yang dihasilkan satisfiable.

Ide tersebut dapat diilustrasikan pada gambar dibawah ini

Pembuktian:
* Asumsi:
:w 	: input
:A	: language
: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)
* Formula:

* φcell: terlihat setiap cell berisi paling tidak 1 symbol, dan setiap cell berisi tidak lebih dari 1 simbol yang berbeda.

* φstart: terlihat setiap cell dari baris pertama memiliki sebah symbol yang berkorespondensi dengan konfigurasi awal dimana input adalah w.

* φaccept: minimal 1 cell merupakan accept state

* φmove mengecek apakah setiap window 2x3 adalah legal sesuai dengan aturan transisi dari mesin turing.

* Ketika Si,j adalah kumpulan window legal(i,j), dan Ui,j adalah kumpulan dari semua window (i,j), maka:

* sehingga kumpulan dari window legal adalah finite.
* Jika φ satisfiable, maka

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

## Referensi