Teorema Cook: Perbedaan antara revisi
Konten dihapus Konten ditambahkan
kTidak ada ringkasan suntingan |
kTidak ada ringkasan suntingan |
||
Baris 1:
{{paragraf_pembuka|date=2012}}
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 name="cook">[http://amturing.acm.org/award_winners/cook_n991950.cfm ].</ref>
Teorema Cook-Levin atau dikenal juga dengan teorema Cook menyatakan bahwa : <ref name="proof">[http://cfile7.uf.tistory.com/attach/20712D0C4B84A8003D040B ].</ref>
'''Problem satisfiabiity (SAT) adalah NP-complete'''
Terdapat 2 cara dalam pembuktian untuk teorema ini yaitu <ref name="proof" />:
# SAT adalah NP
# Setiap problem NP dapat direduksi menjadi SAT dalam waktu polinomial
Langkah - langkah pembuktian <ref name="proof" />:
'''SAT adalah NP'''
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.
| |||