理查德·卡普（Richard Karp，1935年1月3日 - ），美国计算机科学家，1985年图灵奖得主。致力于算法理论研究，包括开发用于网络流和其他组合优化的高效算法问题，多项式时间可计算性与算法效率的直观概念的识别，以及最显著的对NP完备性理论的贡献。

理查德·卡普于1935年1月3日出生于美国马萨诸塞州波士顿的一个犹太裔家庭，父亲是亚伯拉罕·卡普（Abraham Karp），母亲是萝丝·卡普（Rose Karp），卡普从小在为犹太人居住的波士顿多尔切斯特社区长大。

卡普就读于波士顿拉丁学校，在1955年、1956年和1959年获得哈佛大学数学和应用数学的学士、硕士、博士学位。

毕业之后，卡普加入了纽约州约克镇的 IBM 沃森研究中心，并在那里工作到 1968 年。在此期间，卡普在并行计算模型方面做了基础工作，该模型涉及同时使用多台协调的计算机来解决耽搁问题。

1968年，卡普搬到加州大学伯克利分校，担任计算机科学和运筹学专业的职务，因为他对教学的奉献精神为他赢得了 1986 年加州大学伯克利分校杰出教学奖。

卡普在伯克利最初的研究重点是针对硬组合问题的启发式算法，特别是针对出了名的「困难的旅行推销员问题（TSP）」。卡普在1972年发表《组合问题中的可简化性》为有效解决方案提供了令人信服的解释，这也是卡普职业生涯中最重要的论文之一。

旅行推销员问题，也叫旅行商问题「Travelling salesman problem，TSP」，给定一系列城市和每队城市之间的距离，求解访问每一座城市一次并回到起始城市的最短路径。它是组合优化中的一个NP难题，在运筹学和理论计算机科学中非常重要。

卡普在NP完备性方面的工作极大地激发了数学家和计算机科学家对著名的未解决的 P = NP 问题的讨论以及对其的进一步研究。该问题不仅被认为是理论计算机科学中最重要的开放性问题，也是数学中最重要的开放性问题之一。

在发表关于 NP 完备性的论文第二年，卡普与杰克·埃德蒙兹（Jack Edmonds）和约翰·霍普克罗夫特（John Hopcroft）合著了两篇非常重要的论文，内容涉及网络流和二分图匹配的高效算法。

卡普研究的另一个主题是在高效算法的涉及和分析中使用概率。卡普对算法概率分析的兴趣始于1980年代，当时他研究了特定算法的平均运行时间而不是最坏情况的运行时间问题。

卡普在1990年代还对计算生物学进行了研究，当时该领域在人类基因组计划的影响下开始迅速发展。卡普首先检查了基因的物理定位，设计了算法来帮助确定基因组中基因的物理位置。因为有关基因位置的间接实验信息有限，在负担得起全DNA测序可用之前，此类算法尤为重要。从那时起，卡普就研究了生物学中的各种算法问题，例如：确定蛋白质相互作用；不同数据采集技术下的基因图谱设计与分析方法；针对群体遗传学和家族谱系分析中出现的问题设计和分析方法；寻找基因序列中的重复模式和结构；构建和分析代表生物相互作用的网络。

1995年，卡普离开伯克利前往华盛顿大学计算机科学系，还兼职了分子生物技术的兼职教授。他于1999年回到伯克利，担任计算机科学、数学和生物工程方面的职务。

2012年，卡普创建了加州大学伯克利分校的西蒙斯研究所。

参考资料

1. https://amturing.acm.org/award_winners/karp_3256708.cfm
2. https://baike.baidu.com/item/%E7%90%86%E6%9F%A5%E5%BE%B7%C2%B7%E5%8D%A1%E6%99%AE/10730668
3. https://www.britannica.com/biography/Richard-Karp
4. https://liuyandong.com/archives/10313