Pada tahun 1967, Manuel Blum mengembangkan sebuah teori kompleksitas aksiomatik berdasarkan axiom-nya dan membuktikan hasil penting, yang disebut, teorema kecepatan. Bidang ini benar-benar mulai berkembang pada tahun 1971 ketika peneliti AS Stephen Cook dan, bekerja secara independen, Leonid Levin di Uni Soviet, membuktikan bahwa ada masalah yang praktis relevan yang lengkap dengan NP. Pada tahun 1972, Richard Karp mengambil ide ini melompat ke depan dengan kertas landmark-nya, "Reducibility Among Combinatorial Problems", di mana ia menunjukkan bahwa 21 beragam kombinatorial dan masalah teoritis grafik, masing-masing terkenal karena komputasinya tidak jelas, adalah NP-lengkap.
Apa teori yang terlibat oleh axiom Manuel Blum?
teorema kecepatan teorema kecepatan teorema kecepatan