Pada tahun 1967, Manuel Blum mengembangkan teori kompleksitas aksiomatik berdasarkan aksioma-nya dan membuktikan hasil penting, yang disebut, teorema percepatan. Lapangan ini benar-benar mulai berkembang pada tahun 1971 ketika peneliti AS Stephen Cook dan, yang bekerja secara mandiri, Leonid Levin di USSR, membuktikan bahwa ada masalah praktis yang relevan yang lengkap dengan NP. Pada tahun 1972, Richard Karp mengambil ide ini lompatan ke depan dengan makalahnya yang terkenal, "Reducibilitas Diantara Masalah Combinatorial", di mana ia menunjukkan bahwa 21 masalah kombinatorial dan grafik teoretis yang beragam, masing-masing terkenal karena sifat tidak praktis komputasinya, lengkap NP.
Siapa yang membuktikan bahwa ini ada masalah praktis yang relevan yang dilengkapi NP pada tahun 1961?
Stephen Cook dan, bekerja secara mandiri, Leonid Levin
Stephen Cook dan, yang bekerja secara mandiri, Leonid Levin
Siapa PRI
yang PRR
membuktikan VBT
bahwa CSN
ini ART
ada VBI
masalah NNO
praktis ADJ
yang PRR
relevan ADJ
yang PRR
dilengkapi VBP
NP NNO
pada PPO
tahun NNO
1961 NUM
? PUN