理查德·卡普（Richard Karp）

理查德·卡普（Richard Karp）是美国计算机科学家、加州大学伯克利分校教授，因在算法理论和计算复杂性方面的贡献获得1985年图灵奖，是NP完全性理论的重要奠基人之一。

概述

卡普1935年生于波士顿，早年在哈佛大学获博士学位。1972年他发表著名论文，将库克提出的可满足性问题归约到21个经典组合优化问题上，证明它们同属NP完全类。这一工作使人们认识到大量看似不同的实际问题在计算难度上本质相同，若其中一个能被高效求解，则全部都能。

核心贡献

• 卡普的21个NP完全问题：包括旅行商、图着色、装箱、集合覆盖等，奠定了复杂性分类的基础。
• 多项式时间归约：系统化地用归约方法比较问题难度，成为算法分析的标准工具。
• 网络流与匹配算法：提出高效的最大流与二部图匹配方法，如埃德蒙兹与卡普算法。
• 随机化算法与在线算法的早期研究。

应用场景

NP完全理论指导工程师判断哪些问题不宜追求最优精确解，转而采用近似算法、启发式或求解器。物流调度、芯片布线、资源分配、编译优化和生物信息学都依赖对问题复杂性的判断。网络流算法则广泛用于运输规划、图像分割与推荐系统。

常见问题

问：NP完全意味着问题无解吗？答：不是。NP完全问题都有解，只是目前没有已知的多项式时间精确算法，规模大时求最优解会非常耗时，实践中常用近似方法应对。

问：卡普和库克是什么关系？答：库克在1971年提出可满足性问题的NP完全性，卡普次年将其推广到众多组合问题，二者共同奠定了这一理论，都获得了图灵奖。