Richard Karp 1972 年的这篇论文是复杂性理论的分水岭：它把「哪些问题本质上一样难」从零散观察变成了可操作的方法。核心贡献是把 Cook 的可满足性结果转成一套归约技术——用多项式时间变换把 SAT 不断映射到覆盖、匹配、装填、路由、分配与排序等具体问题，从而一次性指出一大批经典未解问题彼此等价：要么都有多项式算法，要么都没有。论文同时给出「完全」的定义与证明范式：只要其中一个有多项式算法，整类都有；反之只要一个难，全都难。这份讲义版 PDF 至今仍是算法课讲归约的原始材料。
🔑 核心要点
方法而非单点结果：用多项式时间变换把 SAT 当种子，向各领域传播「完全」这一属性。
抽象定义清楚：L 可归约到 M 指存在多项式可计算函数 f 使 f(x)∈M ⇔ x∈L；完全的语言要么全在 P 里，要么全不在，前者当且仅当 P=NP。
We show that a large number of classic unsolved problems of covering, matching, packing, routing, assignment and sequencing are equivalent, in the sense that either each of them possesses a polynomial-bounded algorithm or none of them does.