Teorema Cook: Perbedaan antara revisi
Konten dihapus Konten ditambahkan
Menyunting ejaan |
k Menambahkan prana balik Tag: VisualEditor Suntingan perangkat seluler Suntingan peramban seluler Tugas pengguna baru Tugas pengguna baru: pranala |
||
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>
| |||