組合問題之間的可歸約性
二十一道經典難題，原來全是同一道難題的化身。
二十一道困住不同領域數十年的著名難題，竟悄然原是同一道難題。
把這個想法拆開看
有些問題容易檢查，卻似乎難解得嚇人。遞給我一張填好的數獨，我幾秒鐘就能驗對；可讓我從空白填起，那就難多了。一大族實際問題——排程、路由、裝箱、座次安排——都有這種「失衡」的脾性：一個給出的答案很快就能查驗，要找出一個答案，卻似乎需要一場幾乎不可能的搜尋。
Karp 的論文表明，其中二十一個問題不只是相像，而是可以互換。他找到一種辦法，把其中任何一個忠實地翻譯成另一個，忠實到：只要其中一個有了快速解法，便立刻給出全部的快速解法。在一個精確的意義上，它們是同一道難題，套著二十一身行頭。
它從哪裡來
1971 年，Stephen Cook 證明了一個邏輯問題——可滿足性，即判定一團彼此糾纏的「真/假」條件能否同時被滿足——在一個精確的問題類裡是「最難的」。這是個漂亮的結果，但它看起來或許只關乎那一個問題。第二年，在紐約近郊一場 IBM 的研討會上，Richard Karp 接過 Cook 的工具一路推進，靠一連串巧妙的翻譯，證明二十一個廣為人知的問題全都同樣難。一夜之間，這個結果不再是奇珍，而成了一張地圖。
它為何重要
在 Karp 之前，一個被難題困住的研究者，分不清自己是漏了某個巧招，還是撞上了某種真正不可能的東西。在 Karp 之後，有了一個檢驗：證明你的問題就是這些之一——或能歸約到其中之一——你便證明了無人擁有解它的快速辦法，因為一個快速辦法會一舉攻破千百道著名難題。他把「我解不出這個」，變成了「這可證地與我們所知最難的問題一樣難」。
一個打比方
想像一面牆上有二十一道上了鎖的門，每道據說都需要自己那把特製的鑰匙。Karp 造了一套轉接器：一個能把任何一道門的鑰匙變成另一道門鑰匙的裝置。還沒人找到任何一把鑰匙——但如今人人都知道，第一個撬開任何一把鎖的人，就同時打開了所有的門。這樣一把鑰匙到底存不存在，正是那個著名的「P 是否等於 NP」之問，至今無解。
它落在哪裡
1971 年 Cook 劃著了火柴；1972 年 Karp 把它燒成篝火；而身在蘇聯的 Leonid Levin，獨立地擦出了同一束火花。他們的思想——NP 完全性——與圖靈 1936 年關於「電腦究竟能做什麼」的界限並立：圖靈問的是「什麼是可計算的」，Cook 與 Karp 問的是「什麼是可以快速計算的」。他們框定的那個問題，「P 是否等於 NP」，如今是數學中最偉大的未解難題之一。
A large class of computational problems involve the determination of properties of graphs, digraphs, integers, arrays of integers, finite families of finite sets, boolean formulas and elements of other countable domains.