Revisi per 7 April 2013 05.43 sunting EmausBot (bicara \| kontrib) Bot 582.745 suntingan k Bot: Migrasi 15 pranala interwiki, karena telah disediakan oleh Wikidata pada item d:Q377276 ← Revisi sebelumnya		Revisi per 5 Oktober 2016 01.04 sunting balikkan AABot (bicara \| kontrib) Bot, Pengecualian blokir IP 914.197 suntingan k Robot: Perubahan kosmetika 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 14: 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''' Baris 39: :A : language :N : mesin turing NP yang menentukan A :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. Baris 52: 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 Baris 73: </gallery> * sehingga kumpulan dari window legal adalah finite. * Jika φ satisfiable, maka <gallery> Berkas:Pict0.png

Teorema Cook: Perbedaan antara revisi