理查德·卡普

理查德·卡普,在全理查德·曼宁卡普(生于1935年1月3日,波士顿,麻萨诸塞州,美国),美国数学家和计算机科学家,1985年点图灵奖,最高的荣誉计算机科学“他的持续贡献算法理论包括有效的发展算法对网络流量和其他组合优化问题,确定多项式时间可计算性与直观的算法的概念效率,最值得注意的是,对理论的贡献np完全”。他的研究兴趣包括计算机科学理论、组合算法离散型概率,计算生物学,互联网算法。

卡普了学士学位(1955)硕士学位(1956年)和博士学位(1959),都在数学,从哈佛大学。完成学业后,他当过数学家IBM(1959 - 68)之前学术界。卡普在职位上加州大学伯克利分校(1968 - 94)华盛顿大学伯克利(1995 - 99),(1999 -),他作为一个大学教授返回。2012年,他创立了西蒙斯的理论计算研究所伯克利,担任主任直至2017年。

卡普的1972年的论文“还原性组合问题”证明许多常见组合问题是变异的研究相同的问题,这意味着他们都是可能的(np完全问题,问题没有有效的解决方案算法是已知的)。卡普的作者计算的复杂性(1974)和持有专利一种multiconnection交换网络。

除了图灵奖,卡普收到了Fulkerson离散数学奖(1979),美国国家科学奖章(1996),哈佛大学纪念勋章(1997),以色列理工学院的哈维奖(1998),卡内基梅隆大学的迪克森科学奖(2008)、(2008)和日本的京都奖。他被选为纽约科学院(1980),美国国家科学院(1980)美国艺术和科学院(1985年),该研究所的组合及其应用(1990)美国科学促进会(1991),美国国家工程院院士(1992)美国哲学协会(1994),法国科学院(2002),和欧洲科学院(2004)。