理查德·卡普

1972年发表的论文《组合问题间的可归约性》（Reducibility Among Combinatorial Problems）确立了理查德·卡普在计算复杂性理论中的核心地位。通过证明21个不同的问题是NP完全问题，他为研究人员提供了一种必要的方法论，用以识别计算机科学中哪些理论和实践挑战在使用高效多项式时间算法求解时在本质上是困难的。

学术基础与早期职业生涯

理查德·曼宁·卡普于1935年出生在波士顿，他在哈佛大学完成了全部正规教育。他于1955年获得学士学位，1956年获得硕士学位，并于1959年在哈佛大学工程与应用科学学院获得应用数学博士学位。学业结束后，他在IBM托马斯·J·沃森研究中心开启了自己的职业生涯。

组合算法的发展

卡普的工作涵盖了数十年的算法开发。1962年，他与迈克尔·赫尔德合作创建了用于旅行商问题的赫尔德-卡普算法。随后，他在1971年与杰克·埃德蒙兹共同开发了用于解决网络最大流问题的埃德蒙兹-卡普算法。1973年，他与约翰·霍普克罗夫特合作开发了霍普克罗夫特-卡普算法，该算法至今仍是识别二分图中最大基数匹配的最快方法。此外，他还在1987年与迈克尔·O·拉宾共同开发了拉宾-卡普字符串搜索算法。

机构职务与荣誉

1968年，卡普加入加州大学伯克利分校任教，并担任计算机科学系的首任副系主任。除了在华盛顿大学担任过四年教授外，他一直保持着与伯克利分校的联系。2012年，他成为西蒙斯计算理论研究所的创始所长。他对科学的贡献获得了众多荣誉，包括1985年的图灵奖、1998年的哈维奖、2004年的本杰明·富兰克林奖章、2008年的京都奖以及2009年的迪克森奖。

快速事实

- 出生日期：1935年，马萨诸塞州波士顿 - 教育背景：哈佛大学（学士、硕士、博士） - 主要所属机构：加州大学伯克利分校 - 图灵奖：1985年 - 京都奖（先进技术）：2008年 - 主要研究领域：生物信息学与计算理论 - 1972年主要论文：《组合问题间的可归约性》 - 创始所长：西蒙斯计算理论研究所

读者常见问题

### 理查德·卡普1972年论文的意义是什么？

它证明了21个不同的问题是NP完全问题，为分类问题的计算难度提供了一种标准方法论。

### 理查德·卡普获得了哪些主要奖项？

他获得了图灵奖、京都奖、哈维奖、本杰明·富兰克林奖章以及约翰·冯·诺依曼理论奖等。