组合问题之间的可归约性
二十一道经典难题，原来全是同一道难题的化身。
二十一道困住不同领域数十年的著名难题，竟悄然原是同一道难题。
把这个想法拆开看
有些问题容易检查，却似乎难解得吓人。递给我一张填好的数独，我几秒钟就能验对；可让我从空白填起，那就难多了。一大族实际问题——排程、路由、装箱、座次安排——都有这种「失衡」的脾性：一个给出的答案很快就能查验，要找出一个答案，却似乎需要一场几乎不可能的搜索。
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.