Teorema Cook: Perbedaan antara revisi
Konten dihapus Konten ditambahkan
Menyunting ejaan |
Tidak ada ringkasan suntingan |
||
| (Satu revisi perantara oleh satu pengguna lainnya 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>
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 30 ⟶ 27:
Ide tersebut dapat diilustrasikan pada gambar dibawah ini
Pembuktian:
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 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'''.
| |||