今天我们要介绍一位被誉为“三栖学者”的传奇人物——理查德·卡普（Richard Manning Karp）。他在1985年获得了备受瞩目的图灵奖。

理查德·卡普之所以被称为“三栖学者”，是因为他在多个学科领域都有着深厚的造诣。他在加州大学伯克利分校同时担任电气工程和计算机系、数学系以及工业工程和运筹学系的教授。这种跨学科的聘任在美国大学中实属罕见。卡普获得图灵奖，是因为他在算法设计与分析、计算复杂性理论以及随机化算法等诸多方面作出了开创性的贡献。

理查德·卡普于1935年1月3日出生在马萨诸塞州波士顿的一个犹太裔家庭。父亲是亚伯拉罕·卡普（Abraham Karp），母亲是萝丝·卡普（Rose Karp）。他有三个弟妹，分别是罗伯特（Robert）、大卫（David）和卡罗琳（Carolyn）。卡普在当时主要为犹太人居住的波士顿多尔切斯特社区的一间小公寓里长大。

卡普的父母都是哈佛大学的毕业生。母亲在参加夜校课程后，最终在57岁时获得了哈佛大学的学位。父亲在哈佛大学毕业后，曾有就读医学院的梦想，但由于无力支付学费，最终成为了一名数学教师。卡普本人也就读于哈佛大学，1955年获得学士学位，1956年获得硕士学位，1959年获得应用数学博士学位。此后，他开始在IBM的托马斯·J·沃森研究中心工作。

他从小就展现出广泛的兴趣和过人的聪明才智。在哈佛大学期间，他文理兼修，先后于1955年获得文学学士学位，1956年获得理科硕士学位。随后，他在哈佛大学计算实验室攻读博士，并于1959年取得应用数学博士学位。完成学业后，他在IBM位于Yorktown Heights的沃森研究中心工作了近十年。

20世纪50年代末至60年代，是计算机科学的创立时期，计算机应用开始受到社会重视并逐渐普及。卡普在IBM期间，深入研究了与实际应用密切相关的一系列数学问题，如路径问题、背包问题、覆盖问题、匹配问题、分区问题和调度问题等，取得了许多卓越的成果。这些问题的一个共同特点是，当图中增加一个节点时，需要考察的可能解的数目急剧增加，形成所谓的“组合爆炸”（combinatorial explosion），使计算机的计算量大幅增加，甚至难以实现。

以路径问题中著名的旅行推销员问题为例，在卡普之前，最好的结果是由Rand公司的丹齐格、福格申和约翰逊通过手工和计算机结合的方法求得的49个城市的最佳路线。卡普与他的同事海尔特经过反复研究，提出了一种新的“分枝限界法”（branch-and-bound method）。这种方法使得旅行推销员能周游的城市数达到65个，打破了由Rand公司保持的记录。

分枝限界法是一种构造性的探索方法，能够在整个允许的解空间中进行最优搜索。其核心在于对解集合反复进行分枝，每次分枝时计算最优解的界限。如果某个子集的界限不优于已知的允许解，则抛弃该子集；否则继续分枝，直到子集仅含一个解。尽管分枝限界法本质上是一种策略而非具体算法，但由于其在解决许多问题中非常实用，常被称为“分枝限界算法”，几乎在所有算法书籍中都有介绍。

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

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

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类中的“最困难”问题时，提出了一种不同于库克归约的多项式时间归约方法，称为“多项式时间多一归约”，有时直接被称为“卡普归约”。

除了前述贡献之外，理查德·卡普在组合优化算法的概率分析和随机化算法方面也取得了重要成果。近年来，卡普还致力于并行算法的研究，并有所创新。1996年11月，卡普与他在伯克利的同事库勒（D．Culler）等人在《ACM通讯》（Communications of ACM）上发表了一篇论文，提出了一种名为LogP的并行算法实用模型。这种模型的优点在于能够客观科学地概括分布存储器并行系统的通信开销，因而引起了学术界的广泛关注。我国中科院计算所的学者基于LogP模型设计并实现了一种并行计算模拟器，取得了良好的效果，详情可参阅《计算机研究与发展》1997年9月刊。

卡普因其多方面的贡献，获得了许多荣誉与奖项。除了图灵奖之外，他还在1978年获得了美国运筹学与工业管理学会颁发的兰彻斯特奖（Lanchester Prize），1979年获得美国数学会授予的富尔克森奖（Fulkerson Prize），1990年获得美国运筹学会的冯·诺伊曼理论奖（von Neumann Theory Prize），1995年获得巴贝奇奖（Babbage Award），1996年获得美国科学院授予的全国科学奖章（National Medal of Science）。早在1980年，卡普就已当选为美国科学院院士。

卡普是在1985年10月于科罗拉多州丹佛召开的ACM年会上接受图灵奖的。他的图灵奖演讲题为“组合论、复杂性和随机性”（Combinatorics, Complexity, and Randomness），这是对上述课题的精彩综述，并且提供了一张有关组合优化和计算复杂性理论发展过程的年表，涵盖了从1900年德国数学家希尔伯特提出“23个数学难题”开始，到20世纪80年代中期的进展和成果，具有很高的参考价值。

目前，他还建在，今年89岁。祝老爷子长命百岁，或者长命120岁。

No447.第20届图灵奖得主，全家都是哈佛毕业的理查德·卡普 18:52 Share

软件那些事儿

Shownotes Transcript

No447.第20届图灵奖得主，全家都是哈佛毕业的理查德·卡普