Revisi per 24 Juni 2021 07.35 sunting InternetArchiveBot (bicara \| kontrib) Bot 695.977 suntingan Rescuing 1 sources and tagging 0 as dead.) #IABot (v2.0.8 ← Revisi sebelumnya		Revisi per 23 Mei 2022 12.54 sunting balikkan Rrunitis (bicara \| kontrib) 138 suntingan Menyunting ejaan Tag: VisualEditor Tugas pengguna baru Tugas pengguna baru: pranala Revisi selanjutnya →
Baris 4: Teorema Cook-Levin atau dikenal juga dengan teorema Cook menyatakan bahwa: '''''Problem ~~satisfiabiity~~satisfiability'' (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> Terdapat 2 cara dalam pembuktian untuk teorema ini yaitu: Baris 12: Langkah - langkah pembuktian: '''SAT adalah NP''' 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<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. Baris 29: * Lakukan pengecekan apakah formula boolean yang dihasilkan satisfiable. Ide tersebut dapat ~~dilustrasikan~~diilustrasikan pada gambar dibawah ini <gallery> Berkas:Pict3.png Baris 43: * 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~~invalid, 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>) Baris 64: Berkas:Pict7.png </gallery> * φ<sub>move</sub> mengecek apakah ~~seyiap~~setiap window 2x3 adalah legal sesuai dengan aturan transisi dari mesin turing. <gallery> Berkas:Pict8.png

Teorema Cook: Perbedaan antara revisi