理查德·卡普

理查德·卡普 - 简介

理查德·卡普（Richard Karp）1935年1月3日生于波士顿，从小时起就兴趣广泛，聪明过人。在哈佛大学时他文理兼修，1955年先获得文学学士学位，第二年又获得理科硕士学位。之后他进入哈佛大学的计算实验室攻读博士，于1959年取得应用数学博士学位。理查德·卡普教授现任美国加州大学伯克利分校计算机科学讲座教授，美国科学院、美国工程院、美国艺术与科学院、欧洲科学院院士。因其在计算机科学领域的基础贡献曾获图灵奖、冯诺依曼奖、美国国家科学勋章、哈佛大学百年奖章等奖项，还担任美国科学院会刊（PNAS）等多个国际著名刊物编委。

理查德·卡普 - 历程

简历

卡普1935年1月3日生于波士顿，从小时起就兴趣广泛，聪明过人。在哈佛大学时他文理兼修，1955年先获得文学学士学位，第二年又获得理科硕士学位。之后他进入哈佛大学的计算实验室攻读博士，于1959年取得应用数学博士学位。

学成以后，他进入IBM位于Yorktown Heights的沃森研究中心，在那里工作近10年。从20世纪50年代末至60年代，正是计算机科学的创建时期，高级语言刚诞生不久，计算机应用开始被社会所重视并逐渐走向普及。在这种情况下，有关数据结构、算法、计算复杂性等课题吸引着众多学者的注意。IBM作为美国乃至世界最大的计算机厂商，理所当然地成为这些研究的中心之一，集中了大批最优秀的研究人员。

卡普在IBM期间，主要是深入研究了与实际应用有密切联系的一系列数学问题，如路径问题、背包问题、覆盖问题、匹配问题、分区问题、调度问题等，取得了许多出色的成果。这些问题有一个共同的特点，即如果用图来表示问题，那末当图中增加一个结点时，需要考察的可能的解的数目就急剧增加，形成所谓“组合爆炸”（combinatorial explosion），使计算机的计算工作量大大增加，到一定程度就根本无法实现。以路径问题中最著名的旅行推销员问题为例，在卡普以前，最好的结果是Rand公司的丹齐格（George Benard Dantzig）、福格申（R．Fulkerson）和约翰逊（S．Johnson）用手工和计算机相结合的办法，求出了包含49个城市的旅行推销员的最佳路线。卡普和他的同事海尔特(M．Held)经过反复研究，终于提出了一种称为“分枝限界法”（branch—and—bound method）的新方法，用这种新方法实现的算法使旅行推销员能周游的城市数达到65个，从而打破了由Rand公司保持的记录。

分枝限界法

分枝限界法是一种构造性的探索法，可在整个允许的解空间中进行最优搜索。该方法的要点是：对解集合反复进行分枝，每次分枝时，都对所得的子集计算最优解的界。如果对某个子集求得的界不优于已知的允许解，则抛弃此子集不再进行分枝；否则继续分枝以探索更好的解，直到所得的子集仅含有一个解时为止。分枝限界法就其实质而言是一种求解策略而非算法，具体算法要根据实际问题的特点去实现。但由于这种方法在求解许多问题中都非常实用，因此常常被直呼为“分枝限界算法”，在几乎任何一本有关算法的书中都有介绍。

网络流问题

卡普还研究过最大网络流问题。这个问题给定一个包含起点和终点的有向图，其中的每条边都有一定的容量限制。如果把边想象成管道，在其中流过某种物质，需要求出从起点到终点的最大物流量。这个问题对于输油管道、输气管道、公路网、通信网的设计都有很重要的意义。解决这个问题的第一个算法是福特（L．Ford）和福格申（O．R．Fulkerson）在1956年提出的，算法的要点是：从流量0开始，反复寻找满足如下条件的所谓增量路径：既能向该路径中注入尽可能大的流量，又能保证所有的边不超出饱和状态，直至无法找到新的增量路径为止。这个算法在多数情况下是有效的，但在某些特殊情况下效率很低，甚至无法给出答案。卡普和埃德蒙多（J．Edmonds）合作，在1969年对这个算法进行了改进，每次在寻找增量路径时选择包含的边数最少的路径，从而使算法的效率大大提高。改进后的算法的运行时间正比于结点数和边数平方的乘积。

研究和发现

在对旅行推销员问题进行研究的过程中，卡普发现，无论对算法作何种重大的改进，也无论用何种更高效的新算法使旅行推销员能周游的城市数进一步增加（包括后来采用一种称为“多面体组合学”的方法把它转变为线性规划问题，从而使周游城市数超过300），解题所需的时间总是问题规模（在这里是城市数）的函数，且以指数方式增长。这引起卡普的深思，并促使他进入计算复杂性领域进行更深层次的研究。1967年，正好以色列学者、计算复杂性理论研究的先驱拉宾（M．Rabin，1976年图灵奖获得者）从希伯莱大学来到IBM公司的沃森研究中心作客座研究员，并且和卡普住在同一公寓大楼(卡普长期单身，直到1979年44岁才结婚成家），他们成了朋友，经常一起上下班，一起散步，拉宾在计算复杂性理论方面的深刻见解给了卡普很多启发。

1968年，卡普离开IBM到加州大学伯克利分校工作。这里是计算机科学理论的又一个研究中心，库克(S．Cook，1982年图灵奖获得者)、布卢姆(M．Blum，1995年图灵奖获得者)等一批知名学者当时都在那里，学术气氛十分浓厚。布卢姆是计算复杂性理论的主要奠基人之一，库克则于1971年最早提出“NP完全性”问题。在这样的环境下，卡普对计算复杂性问题的研究日益深入。

发表重要论文

1972年，卡普发表了他的那篇著名的论文：“组合问题中的可归约性”(Reducibility among Combinatorial Problems，见由R．E．Miller和J．W．Thatcher所编纂，由Plenum出版社出版的Complexity Of Computer Computations一书)。卡普的论文发展和加强了由库克提出的“NP完全性”理论，尤其是，库克仅证明了命题演算的可满足问题是NP完全的，而卡普则证明了从组合优化中引出的大多数经典问题，包括背包问题、覆盖问题、匹配问题、分区问题、路径问题、调度问题等，都是NP完全问题。只要证明其中任一个问题是属于P类的，就可解决计算复杂性理论中最大的一个难题，即P=NP。这就是卡普论文的主要贡献和主要意义。

这篇论文还有另外一些贡献。其一就是对计算复杂性理论中的术语进行了规范和统一。把有多项式时间算法的问题命名为P类问题，就是卡普在这篇论文中首次采用的，现在已为学术界所接受并普遍采用，这为学术交流带来了很大的好处。其二是卡普在刻画NP类中的“最困难”问题类时，提出了与库克归约不同的另一种归约方法，称作“多项式时间多一归约”，有时直接把它叫做“卡普归约”。卡普归约的要点如下：对于∑上的两个语言L1、L2，在多项式时间可计算函数f:∑*→∑*，使得对任何x∈∑*，x∈L1当且仅当f(x)∈L2，则称L1多项式时间多一归约到L2，记为L1≤pmL2。这时，x∈Ll的判别可以通过计算f(x)，转化成f(x)∈L2的判别。因此，Ll≤pmL2：更直观地理解为11的计算难度不比上2大。同库克归约中的≤pt类似，≤pm也可定义在任何语言类D上，若存在L∈D，使对于任何L’∈D，都有L’，≤pmL，则称乙为D—m完全的。其三，卡普的论文给出了“多项式谱系”或叫“多项式层次”(polynomial hierarchy)的基本思想。

多项式谱系

所谓多项式谱系，就是从库克归约和卡普归约出发，可建立P和NP类关于任何语言L的相对化定义，再自然推广到任何语言类D上，得：
P(D)=∪P（L），NP（D）=∪NP（L）
L∈D
基于此，可将P和NP视为语言类上的一种算子，且有
D P（D） NP（D），P（P）=，NP（P）=NP
从语言类p开始，将算子NP重复地作用在其上，便产生一个语言类的无穷递增序列：
P，NP，NP(NP)，NP(NP(NP))…
把它们依次记为∑p0,∑p1,∑p2,∑p3…
也即：
∑p0=P，∑Pk+1=NP（∑Pk），K≥0
这就形成了一个基本的复杂性类。此外可以定义与它相关的其他两个复杂性类ⅡPK和Δpk 如下：
ⅡPK=Co-∑Pk={L ∑*|L∈∑Pk }
Richard Karp ΔpO= P，∑Pk+1=p（∑Pk），K≥0
这三种复杂性类有下述基本关系：
ΔpK ∑Pk∩ⅡPK，∑Pk∪ⅡPK ΔPk+1
由此可见，
∪∑Pk ∑Pk∪ⅡPK=∪ΔpK
K≥0 K≥0 K≥0
由∑Pk，ⅡPK及ΔPk (k≥0)所描述的层次结构记为PH，即多项式谱系。
卡普给出了多项式谱系的基本思想后，由迈耶（A．Meyer）和斯托克迈耶（L．Stockmeyer）在1973年给出了严格形式化定义，拉特霍尔(C．Wrathall)又给出了有关定理，成为研究计算复杂性的一个重要工具。

其它贡献

除了以上贡献外，卡普在组合优化算法的概率分析、随机化算法等方面也有不少研究成果。近年来，卡普还致力于并行算法的研究，并有所创造。1996年11月，卡普和他在伯克利时的同事库勒（D．Culler）等人在Communications of ACM上发表论文，提出了名为1ogP的一种并行算法的实用模型。这种模型的优点是对分布存储器并行机系统的通信开销作了比较客观和科学的概括，因而引起学术界的重视。我国中科院计算所的学者已经基于LogP模型设计与实现了一种并行计算模拟器，取得了良好结果，详情请参阅《计算机研究与发展》，1997年9月。

卡普由于其多方面的贡献，获得许多荣誉与奖励。除图灵奖以外，1978年他获得美国运筹学与工业管理学会颁发的Lanchster奖，1979年美国数学会授予他Fulkerson奖，1990年美国运筹学会授予他冯·诺伊曼理论奖，1995年他获得Babbage奖，1996年美国科学院授予他全国科学奖章（National Medal of Science）。早在1980年，卡普就已当选为美国科学院院士。

卡普是在1985年10月于科罗拉多州的丹佛召开的ACM年会上接受图灵奖的。他的图灵奖演说题为“组合论、复杂性和随机性”(Combinatorics，Complexity and Randomness)，是对上述课题的一个精彩综述，并且给出了一张有关组合优化和计算复杂性理论发展过程的年表，从1900年德国数学家希尔伯特提出“23个数学难题”开始，到20世纪80年代中期他演说时为止的进展和成果，很有参考价值。颁奖以后卡普还接受了记者卡伦·弗兰克尔(Kren A．Frenkel)的采访，演说全文和采访时的对话刊载于Communications ofACM，1986年2月，98—117页，或可见《前20年的图灵奖演说集》(ACM Turing Award Lectures ’The First Twenty Years：1966—1985，ACM pr．)，433-466页。

卡普除了在IBM、伯克利工作过以外，还曾在密执安大学、哥伦比亚大学、纽约大学和布鲁克林(Brooklyn)理工学院任教。目前则在华盛顿大学计算机科学系，其电子信箱为: karp@cs.washington.edu 。

理查德·卡普 - 荣誉

获得1985年度的图灵奖：有“三栖学者”美称的理查德·卡普（Richard Manning Karp）获得1985年度的图灵奖是众望所归的。卡普之所以被称为“三栖学者”是因为他知识渊博，贯通多个学科专业，因而同时被加州大学伯克利分校的电气工程和计算机系、数学系以及工业工程和运筹学系三个系聘为教授。这种情形在美国大学中都是不多见的。而卡普之所以被授予图灵奖，也是因为他在算法的设计与分析、计算复杂性理论、随机化算法等诸多方面作出了创造性贡献。

2008年第24届京都奖：

2008年6月20日，日本稻盛财团在其官方网站上宣布，将2008年第24届京都奖（Kyoto Prize）授予美国和加拿大的三位科学家，以表彰他们对科学发展、文明进步以及人类精神充实和提升的巨大贡献。

京都奖是国际科学大奖，它每年颁发一次，分为先进技术、基础科学以及思想和艺术三大分支奖项。每项获奖者将获得证书、20k金质奖章和5000万日元的奖金。

公告表示，2008年京都奖先进技术奖授予美国加州大学伯克利分校的计算机理论学家Richard Manning Karp，以表彰他对“计算的复杂性理论（theory of computational complexity）发展的基础性贡献”。20世纪70年代，Karp确立了NP完全性理论（NP-completeness），这对算法分析和设计的指导方针具有深远的影响。此外，他还发展了许多实践相关的计算机算法。

京都奖基础科学奖获得者是加拿大多伦多大学教授、西奈山医院Samuel Lunenfeld研究所的Anthony James Pawson，他获奖的原因是“提出并证实了信号传导中的转接分子（Adapter Molecules）概念”。Pawson认为，在信号蛋白中存在特殊的转接器结构SH2，它与特定磷酸化结构域的“绑定”引导了细胞内信号传递路径，这些重要的信号控制着细胞生长和分化。这一认识确立了信号传导的一种基本模式，对随后生命科学的发展做出了重要贡献。

京都奖思想和艺术奖由加拿大麦吉尔大学的退休教授、哲学家Charles Margrave Taylor获得。他“构建了一种追求多元文化共存的社会哲学体系”。

据悉，2008年京都奖颁奖典礼将于11月10日在日本京都国际会议中心举行。 

理查德·卡普 - 受聘

2008年6月18日下午，中关村教学园区S106教室内座无虚席，来自美国加州大学Richard Karp教授受聘担任中科院 “爱因斯坦讲席教授”，研究生院教务长苏刚教授为Karp教授颁发了中科院“爱因斯坦讲席教授”荣誉证书。随后，Karp教授做了题为 “计算机科学是科学的透镜” 的学术报告。

理查德·卡普教授现任美国加州大学伯克利分校计算机科学讲座教授，美国科学院、美国工程院、美国艺术与科学院、欧洲科学院院士，因其在计算机科学领域的基础贡献曾获图灵奖、冯诺依曼奖、美国国家科学勋章、哈佛大学百年奖章等奖项，还担任美国科学院会刊（PNAS）等多个国际著名刊物编委。

计算在各个科学领域日益成为不可或缺的工具，就像望远镜和显微镜一样。Karp教授的报告阐述了这种“计算透镜”的基本科学问题，回顾“计算透镜”如何推动生物学、物理学、经济学、网络科学的进步。在生物学方面，无论是生物分子信息的获取、分类和分析，还是基因的表达与翻译，计算机科学发挥着不可替代的作用。而网络计算的发展必将带来更多的好处，并进一步推动网络科学的发展。Karp教授还介绍加州大学伯克利分校的工作，包括因特网与Web、社会计算、量子计算、统计物理；讨论生物学的计算过程，涉及蚁群行为、代谢通路、分子级进化、蛋白质网络等应用实例。

Karp教授的学术报告结束后，赢得了大家热烈的掌声。同学们的提问十分踊跃。Karp教授亲切地与大家进行了交流，对同学们的提问，Karp教授都一一给出了耐心细致的回答，现场不时发出阵阵笑声。同学们感到与学术大师的直接交流能给大家今后的学术研究带来启发，对今后的学习、工作会产生深刻的影响。

中科院计算所副所长徐志伟研究员、信息学院常务副院长黄庆明教授等出席了学术报告会。