Teorema Cook: Perbedaan antara revisi

Dalam [[Komputasi|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 namun mudah untuk diverifikasi kebenarannya pada kelas P (dalam waktu polinomial). <ref>[http://amturing.acm.org/award_winners/cook_n991950.cfm]</ref>

Teorema Cook-Levin atau dikenal juga dengan teorema Cook menyatakan bahwa :

'''''Problem satisfiabiitysatisfiability'' (SAT) adalah NP-complete'''<ref name="ww">[{{Cite web |url=http://cfile7.uf.tistory.com/attach/20712D0C4B84A8003D040B] |title=Salinan arsip |access-date=2012-05-20 |archive-date=2014-11-13 |archive-url=https://web.archive.org/web/20141113045148/http://cfile7.uf.tistory.com/attach/20712D0C4B84A8003D040B |dead-url=yes }}</ref>

SAT adalah NP karena masukan dari nilai Boolean ke variabel boolean memenuhi satisfiabliity''satisfiablility'' dari suatu ekspresi yang dapat diverifikasikan dalam waktu polinomial oleh sebuah mesin turing deterministik.

contoh : E = (X₁ V ¬X₁ V X₂) Ʌ (X₃ V X₂ V ¬X₁) Ʌ (X₁ V X₂) Ʌ (X₃)

dengan memberikan assignment pada variabel X₁, X₂, X₃. SAT adalah suatu ekspresi dalam bentuk CNF dan satisfiable jika menghasilkan nilai True.

Misal diberikan nilai :

X₁ =T , X₂ = T, X₃ = 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.''' <ref name="ww"/>

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 :'''

Ide tersebut dapat dilustrasikandiilustrasikan pada gambar dibawah ini

Pembuktian :

* Asumsi :

:N menentukan w∈anggota A dalan n^k langkah untuk constanta k

* X_i,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 invaildinvalid, misal : cell berisi ''multiple symbols'' , tidak dimulai dengan input w dan state q₀ , 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 diantaradi antara sebuah state, sebuah alphabet tape, dan sebuah #. (φ _cell)

* Formula :

* φ_cellstart : terlihat setiap cell berisidari palingbaris tidakpertama 1memiliki sebah symbol, danyang setiapberkorespondensi celldengan berisikonfigurasi tidakawal lebihdimana dariinput 1 simbol yangadalah berbedaw.

* φ_startmove :mengecek terlihatapakah setiap cellwindow dari2x3 barisadalah pertamalegal memiliki sebah symbol yang berkorespondensisesuai dengan konfigurasiaturan awaltransisi dimanadari input adalahmesin wturing.

* Jika φ satisfiable, maka