Teorema Cook: Perbedaan antara revisi
Konten dihapus Konten ditambahkan
kTidak ada ringkasan suntingan |
Tidak ada ringkasan suntingan |
||
Baris 1:
'''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). [http://amturing.acm.org/award_winners/cook_n991950.cfm]
Teorema Cook-Levin atau dikenal juga dengan teorema Cook menyatakan bahwa :
'''Problem satisfiabiity (SAT) adalah NP-complete'''<ref name="ww">[http://cfile7.uf.tistory.com/attach/20712D0C4B84A8003D040B]</ref> Terdapat 2 cara 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">
Langkah - langkah pembuktian
'''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.
Baris 15:
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.''' <ref name="ww">
'''Setiap problem NP dapat direduksi menjadi SAT dalam waktu polinomial'''
Baris 77:
</gallery>
* Karena A dapat direduksi menjadi problem SAT dengan input w, dan SAT adalah problem NP, maka terbukti bahwa '''SAT adalah NP-complete'''.
== Referensi ==
{{reflist}}
[[Kategori:Teorema]]
| |||