理查德·卡普的个人简介

　　卡普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公司保持的记录。

　　理查德·卡普的研究和发现

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

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

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

　　理查德·卡普的的重要论文

　　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)的基本思想。