卡普的二十一個NP-完全問題 在計算複雜度理論內一個極度重要的成就是史提芬古克在年證明出了第一個NP完全問題 布爾可滿足性問題在年理查德卡普將這個想法往前推進發表了他著名的論文Reducibility Among Combinatorial Problems其內證明了個不同的均因為其難解而惡名昭彰的組合數學與圖論問題是NP完全問題 藉由展示出許多研究上面重要的問題是NP完全問題卡普促進了研究NPNP完備性以及現在著名的P  NP這些問題