Teorema Cook
Artikel ini perlu diwikifikasi agar memenuhi standar kualitas Wikipedia. Anda dapat memberikan bantuan berupa penambahan pranala dalam, atau dengan merapikan tata letak dari artikel ini.
Untuk keterangan lebih lanjut, klik [tampil] di bagian kanan.
|
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 namun mudah untuk diverifikasi kebenarannya pada kelas P (dalam waktu polinomial).[1]
Teorema Cook-Levin atau dikenal juga dengan teorema Cook menyatakan bahwa: Problem satisfiability (SAT) adalah NP-complete[2]
Terdapat 2 cara dalam pembuktian untuk teorema ini yaitu:
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. [2]
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 mensimulasikan 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
sunting- ^ [1]
- ^ a b c d "Salinan arsip". Diarsipkan dari versi asli tanggal 2014-11-13. Diakses tanggal 2012-05-20.