Wikipedia

Teorema Cook: Perbedaan antara revisi

Jelajahi riwayat secara interaktif
← Revisi sebelumnya
Konten dihapus Konten ditambahkan
VisualTeks wiki
Adi.akbartauhidin (bicara | kontrib)
8.311 suntingan
Tidak ada ringkasan suntingan
Raksasabonga (bicara | kontrib)
15.580 suntingan
Tidak ada ringkasan suntingan
 
(22 revisi perantara oleh 14 pengguna tidak ditampilkan)
Baris 1:
{{wikify}}
{{paragraf_pembuka|date=2012}}
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.
Teorema Cook-Levin atau dikenal juga dengan teorema Cook menyatakan bahwa :
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>
'''Problem satisfiabiity (SAT) adalah NP-complete'''
 
TerdapatTeorema 2Cook-Levin caraatau dalamdikenal pembuktianjuga untukdengan teorema iniCook yaitumenyatakan bahwa:
'''''Problem 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>
# SAT adalah NP▼
# Setiap problem NP dapat direduksi menjadi SAT dalam waktu polinomial▼
 
LangkahTerdapat -2 langkahcara dalam pembuktian untuk teorema ini yaitu:
# SAT adalah NP<ref name="ww"/>
# Setiap problem NP dapat direduksi menjadi SAT dalam waktu polinomial<ref name="ww"/>
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.''' ▼
 
Langkah - langkah pembuktian:
▲# Setiap problem NP dapat direduksi menjadi SAT dalam waktu polinomial
▲# '''SAT adalah NP'''
dapat dinyatakan dalam bentuk sebagai berikut : pict1▼
▲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.
Akan diperlihatkan bahwa untuk setiap A ∈ NP dengan input w, sangat dimungkinkan untuk menghasilkan sebuah formula Boolean yag satisfiable jika w anggota A. ▼
▲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>)
<gallery>
▲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.
Berkas:Pict0.png
▲Misal diberikan nilai :
</gallery>
▲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'''
Ide pembuktian :▼
▲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 dilustrasikandiilustrasikan pada gambar dibawah ini
<gallery>
Berkas:Pict3.png
</gallery>
 
Pembuktian :
* Asumsi :
:w : input
: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 invaildinvalid, 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 diantaradi 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>)
* Sebuah konfigurasi diturunkan dari konfigurasi sebelumnya sesuai dengan aturan transisi pada mesin turing. (φ<sub>move</sub>)
* Harus terdapat sebuah cell berisi accept state. (φ<sub>accept</sub>)
* Formula :
 
<gallery>
* φ<sub>cell</sub>: terlihat setiap cell berisi paling tidak 1 symbol, dan setiap cell berisi tidak lebih dari 1 simbol yang berbeda.
Berkas:Pict12.png
 
</gallery>
* φ<sub>cellstart</sub> : terlihat setiap cell berisidari palingbaris tidakpertama 1memiliki sebah symbol, danyang setiapberkorespondensi celldengan berisikonfigurasi tidakawal lebihdimana dariinput 1 simbol yangadalah berbedaw.
 
<gallery>
* φ<sub>accept</sub> : minimal 1 cell merupakan accept state▼
Berkas:Pict5.png
 
</gallery>
* φ<sub>startmove</sub> :mengecek terlihatapakah setiap cellwindow dari2x3 barisadalah pertamalegal memiliki sebah symbol yang berkorespondensisesuai dengan konfigurasiaturan awaltransisi dimanadari input adalahmesin wturing.
 
<gallery>
* Ketika Si,j adalah kumpulan window legal(i,j), dan Ui,j adalah kumpulan dari semua window (i,j), maka :▼
Berkas:Pict6.png
 
</gallery>
▲* φ<sub>accept</sub> : minimal 1 cell merupakan accept state
<gallery>
Berkas:Pict7.png
</gallery>
* φ<sub>move</sub> mengecek apakah seyiap window 2x3 adalah legal sesuai dengan aturan transisi dari mesin turing.
<gallery>
Berkas:Pict8.png
</gallery>
▲* Ketika Si,j adalah kumpulan window legal(i,j), dan Ui,j adalah kumpulan dari semua window (i,j), maka :
<gallery>
Berkas:Pict13.png
</gallery>
* sehingga kumpulan dari window legal adalah finite.
* Jika φ satisfiable, maka
 
<gallery>
Berkas:Pict0.png
</gallery>
* Karena A dapat direduksi menjadi problem SAT dengan input w, dan SAT adalah problem NP, maka terbukti bahwa '''SAT adalah NP-complete'''.
 
== Referensi ==
[[Kategori:Teorema]]▼
{{reflist}}
 
▲[[Kategori:Teorema]]
[[de:Satz von Cook]]
[[es:Teorema de Cook]]
[[fa:قضیه کوک لوین]]
[[fr:Théorème de Cook]]
[[it:Teorema di Cook]]
[[he:משפט קוק-לוין]]
[[pl:Twierdzenie Cooka]]
[[pt:Teorema de Cook-Levin]]
[[ru:Теорема Кука — Левина]]
[[simple:Cook–Levin theorem]]
[[sr:Кук-Левинова теорема]]
[[tr:Cook-Levin teoremi]]
[[zh:Cook-Levin理論]]
Diperoleh dari "https://wiki-indonesia.club/wiki/Teorema_Cook"