Revisi per 7 Desember 2018 00.07 sunting AABot (bicara \| kontrib) Bot, Pengecualian blokir IP 914.197 suntingan k Bot: Perubahan kosmetika Tag: PAWS [1.2] ← Revisi sebelumnya		Revisi per 23 Juni 2019 18.20 sunting balikkan LaninBot (bicara \| kontrib) Bot 268.871 suntingan k Perubahan kosmetik tanda baca Tag: PAWS [1.2] Revisi selanjutnya →
Baris 3: 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 satisfiabiity (SAT) adalah NP-complete'''<ref name="ww">[http://cfile7.uf.tistory.com/attach/20712D0C4B84A8003D040B]</ref> Baris 13: '''SAT adalah NP''' SAT adalah NP karena masukan dari nilai Boolean ke variabel boolean memenuhi satisfiabliity dari suatu ekspresi yang dapat diverifikasikan dalam waktu polinomial oleh sebuah mesin turing deterministik. contoh : E = (X<sub>1</sub> V ¬X<sub>1</sub> V X<sub>2</sub>) Ʌ (X<sub>3</sub> V X<sub>2</sub> V ¬X<sub>1</sub>) Ʌ (X<sub>1</sub> V X<sub>2</sub>) Ʌ (X<sub>3</sub>) dengan memberikan assignment pada variabel X<sub>1</sub>, X<sub>2</sub>, X<sub>3</sub>. SAT adalah suatu ekspresi dalam bentuk CNF dan satisfiable jika menghasilkan nilai True. Misal diberikan nilai : X<sub>1</sub> =T , X<sub>2</sub> = T, X<sub>3</sub> = 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"/> '''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. <gallery> Baris 25: </gallery> '''Ide pembuktian :''' * 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. Baris 34: </gallery> Pembuktian : * Asumsi : :w : input :A : language Baris 41: :N menentukan w∈anggota A dalan n<sup>k</sup> langkah untuk constanta k * Sebuah variable dapat dinyatakan dalam X<sub>i,j,s</sub> * X<sub>i,j,s</sub> : 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 invaild, misal : cell berisi ''multiple symbols'' , tidak dimulai dengan input w dan state q<sub>0</sub> , 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 #. (φ <sub>cell</sub>) * Konfigurasi pertama harus berhubungan dengan input w dan state awal q. (φ <sub>start</sub>) * Sebuah konfigurasi diturunkan dari konfigurasi sebelumnya sesuai dengan aturan transisi pada mesin turing. (φ<sub>move</sub>) * Harus terdapat sebuah cell berisi accept state. (φ<sub>accept</sub>) * Formula : <gallery> Berkas:Pict12.png </gallery> * φ<sub>cell</sub> : terlihat setiap cell berisi paling tidak 1 symbol, dan setiap cell berisi tidak lebih dari 1 simbol yang berbeda. <gallery> Berkas:Pict5.png </gallery> * φ<sub>start</sub> : terlihat setiap cell dari baris pertama memiliki sebah symbol yang berkorespondensi dengan konfigurasi awal dimana input adalah w. <gallery> Berkas:Pict6.png </gallery> * φ<sub>accept</sub> : minimal 1 cell merupakan accept state <gallery> Berkas:Pict7.png Baris 68: Berkas:Pict8.png </gallery> * Ketika Si,j adalah kumpulan window legal(i,j), dan Ui,j adalah kumpulan dari semua window (i,j), maka : <gallery> Berkas:Pict13.png

Teorema Cook: Perbedaan antara revisi