Teorema Cook: Perbedaan antara revisi
Konten dihapus Konten ditambahkan
Rescuing 1 sources and tagging 0 as dead.) #IABot (v2.0.8 |
Tidak ada ringkasan suntingan |
||
| (2 revisi perantara oleh 2 pengguna tidak ditampilkan) | |||
Baris 1:
{{wikify}}
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
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
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 21:
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:'''
Baris 29 ⟶ 26:
* Lakukan pengecekan apakah formula boolean yang dihasilkan satisfiable.
Ide tersebut dapat
Pembuktian:
Baris 43 ⟶ 37:
* 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
* 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 49 ⟶ 43:
* Harus terdapat sebuah cell berisi accept state. (φ<sub>accept</sub>)
* Formula:
* φ<sub>cell</sub>: terlihat setiap cell berisi paling tidak 1 symbol, dan setiap cell berisi tidak lebih dari 1 simbol yang berbeda.
* φ<sub>start</sub>: terlihat setiap cell dari baris pertama memiliki sebah symbol yang berkorespondensi dengan konfigurasi awal dimana input adalah w.
* φ<sub>accept</sub>: minimal 1 cell merupakan accept state
* φ<sub>move</sub> mengecek apakah
▲* φ<sub>move</sub> mengecek apakah seyiap 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'''.
| |||