Richard Manning Karp美国数学家和计算机科学家

理查德·曼宁·卡普（Richard Manning Karp，1935年1月3日出生，美国马萨诸塞州波士顿），美国数学家和计算机科学家，并因其“对科学理论的持续贡献”而荣获1985 AM图灵奖，这是计算机科学领域的最高荣誉。这些算法包括开发用于网络流量和其他组合优化问题的高效算法，使用算法效率的直观概念来识别多项式时间可计算性，最值得注意的是对NP完整性理论的贡献。” 他的研究兴趣包括理论计算机科学，组合算法，离散概率，计算生物学和Internet算法。

Karp拥有哈佛大学的数学学士学位（1955年），硕士学位（1956年）和博士学位（1959年）。完成学业后，他在IBM担任数学家（1959–68），然后进入学术界。卡普曾在加州大学伯克利分校（1968–94），华盛顿大学（1995–99）和伯克利分校（1999–）任职，之后又返回大学任教。

Karp于1972年发表的论文《组合问题之间的可约性》证明，许多共同研究的组合问题是同一问题的变体，这意味着它们都可能是棘手的（NP完全问题，即尚无有效求解算法的问题）。Karp是《复杂性计算》（1974）的作者，并拥有一种类型的多连接交换网络的专利。

除了图灵奖外，卡尔普还获得了离散数学富尔克森奖（1979），美国国家科学奖章（1996），哈佛大学百年纪念章（1997），以色列理工学院哈维奖（1998），卡内基·梅隆大学（Carnegie Mellon University）的迪克森科学奖（2008）和日本京都奖（Kyoto Prize）（2008）。他当选为纽约科学院（1980），美国国家科学院（1980），美国艺术与科学学院（1985），组合技术及其应用研究所（1990）和美国科学学会会员。科学进步（1991），美国国家工程院（1992），美国哲学学会（1994），法国科学院（2002）和欧洲科学院（2004）。