Teorema Cook itu apa sih?

Dalam 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).

Teorema Cook-Levin atau dikenal juga dengan teorema Cook menyatakan bahwa:

Problem satisfiability (SAT) adalah NP-complete

Terdapat 2 cara dalam pembuktian untuk teorema ini yaitu: