计算机文化基础系列常识-图灵奖获奖者介绍连载(二十一

1、计算机文化基础系列常识-图灵奖获奖者介绍连载（二十一） 理查德·卡普(Richard Manning Karp)       发明“分枝限界法”的三栖学者    有“三栖学者”美称的理查德·卡普(Richard Manning Karp)获得1985年度的图灵奖是众望所归的。卡普之所以被称为“三栖学者”是因为他知识渊博，贯通多个学科专业，因而同时被加州大学伯克利分校的电气工程和计算机系、数学系以及工业工程和运筹学系三个系聘为教授。这种情形在美国大学中都是不多见的。而卡普之所以

2、被授予图灵奖，也是因为他在算法的设计与分析、计算复杂性理论、随机化算法等诸多方面作出了创造性贡献。    卡普1935年1月3日生于波士顿，从小时起就兴趣广泛，聪明过人。在哈佛大学时他文理兼修，1955年先获得文学学士学位，第二年又获得理科硕士学位。之后他进入哈佛大学的计算实验室攻读博士，于1959年取得应用数学博士学位。学成以后，他进入IBM位于Yorktown Heights的沃森研究中心，在那里工作近10年。从20世纪50年代末至60年代，正是计算机科学的创建时期，高级语言刚诞生不久，计算机应用开始被社会所重视并逐渐走向普及。在这种情况下，有关数据结构、算法

3、、计算复杂性等课题吸引着众多学者的注意。IBM作为美国乃至世界最大的计算机厂商，理所当然地成为这些研究的中心之一，集中了大批最优秀的研究人员。卡普在IBM期间，主要是深入研究了与实际应用有密切联系的一系列数学问题，如路径问题、背包问题、覆盖问题、匹配问题、分区问题、调度问题等，取得了许多出色的成果。这些问题有一个共同的特点，即如果用图来表示问题，那末当图中增加一个结点时，需要考察的可能的解的数目就急剧增加，形成所谓“组合爆炸”(combinatorial explosion)，使计算机的计算工作量大大增加，到一定程度就根本无法实现。以路径问题中最著名的旅行推销员问题为例，在卡普以前，最好的结果

4、是Rand公司的丹齐格(George Benard Dantzig)、福格申(RFulkerson)和约翰逊(SJohnson)用手工和计算机相结合的办法，求出了包含49个城市的旅行推销员的最佳路线。卡普和他的同事海尔特(MHeld)经过反复研究，终于提出了一种称为“分枝限界法”(branchandbound method)的新方法，用这种新方法实现的算法使旅行推销员能周游的城市数达到65个，从而打破了由Rand公司保持的记录。分枝限界法是一种构造性的探索法，可在整个允许的解空间中进行最优搜索。该方法的要点是：对解集合反复进行分枝，每次分枝时，都对所得的子集计算最优解的界。如果对某个子集求得的

5、界不优于已知的允许解，则抛弃此子集不再进行分枝；否则继续分枝以探索更好的解，直到所得的子集仅含有一个解时为止。分枝限界法就其实质而言是一种求解策略而非算法，具体算法要根据实际问题的特点去实现。但由于这种方法在求解许多问题中都非常实用，因此常常被直呼为“分枝限界算法”，在几乎任何一本有关算法的书中都有介绍。    卡普还研究过最大网络流问题。这个问题给定一个包含起点和终点的有向图，其中的每条边都有一定的容量限制。如果把边想象成管道，在其中流过某种物质，需要求出从起点到终点的最大物流量。这个问题对于输油管道、输气管道、公路网、通信网的设计都有很重要的意义。解决这个问题

6、的第一个算法是福特(LFord)和福格申(ORFulkerson)在1956年提出的，算法的要点是：从流量0开始，反复寻找满足如下条件的所谓增量路径：既能向该路径中注入尽可能大的流量，又能保证所有的边不超出饱和状态，直至无法找到新的增量路径为止。这个算法在多数情况下是有效的，但在某些特殊情况下效率很低，甚至无法给出答案。卡普和埃德蒙多(JEdmonds)合作，在1969年对这个算法进行了改进，每次在寻找增量路径时选择包含的边数最少的路径，从而使算法的效率大大提高。改进后的算法的运行时间正比于结点数和边数平方的乘积。    在对旅行推销员问题进行研究的过程中，卡普发

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

8、算复杂性理论方面的深刻见解给了卡普很多启发。    1968年，卡普离开IBM到加州大学伯克利分校工作。这里是计算机科学理论的又一个研究中心，库克(SCook，1982年图灵奖获得者)、布卢姆(MBlum，1995年图灵奖获得者)等一批知名学者当时都在那里，学术气氛十分浓厚。布卢姆是计算复杂性理论的主要奠基人之一，库克则于1971年最早提出“NP完全性”问题。在这样的环境下，卡普对计算复杂性问题的研究日益深入。1972年，卡普发表了他的那篇著名的论文：“组合问题中的可归约性”(Reducibility among Combinatorial Problems，见由

9、REMiller和JWThatcher所编纂，由Plenum出版社出版的Complexity Of Computer Computations一书)。卡普的论文发展和加强了由库克提出的“NP完全性”理论，尤其是，库克仅证明了命题演算的可满足问题是NP完全的，而卡普则证明了从组合优化中引出的大多数经典问题，包括背包问题、覆盖问题、匹配问题、分区问题、路径问题、调度问题等，都是NP完全问题。只要证明其中任一个问题是属于P类的，就可解决计算复杂性理论中最大的一个难题，即P=?NP。这就是卡普论文的主要贡献和主要意义。这篇论文还有另外一些贡献。其一就是对计算复杂性理论中的术语进行了规范和统一。把有多项

10、式时间算法的问题命名为P类问题，就是卡普在这篇论文中首次采用的，现在已为学术界所接受并普遍采用，这为学术交流带来了很大的好处。其二是卡普在刻画NP类中的“最困难”问题类时，提出了与库克归约不同的另一种归约方法，称作“多项式时间多一归约”，有时直接把它叫做“卡普归约”。卡普归约的要点如下：对于上的两个语言L1、L2，在多项式时间可计算函数f:*，使得对任何x*，xL1当且仅当f(x)L2，则称L1多项式时间多一归约到L2，记为L1pmL2。这时，xLl的判别可以通过计算f(x)，转化成f(x)L2的判别。因此，LlpmL2：更直观地理解为11的计算难度不比上2大。同库克归约中的pt类似，pm也可

11、定义在任何语言类D上，若存在LD，使对于任何L'D，都有L'，pmL，则称乙为Dm完全的。其三，卡普的论文给出了“多项式谱系”或叫“多项式层次”(polynomial hierarchy)的基本思想。所谓多项式谱系，就是从库克归约和卡普归约出发，可建立P和NP类关于任何语言L的相对化定义，再自然推广到任何语言类D上，得：P(D)=P（L），NP（D）=NP（L）     LD        基于此，可将P和NP视为语言类上的一种算子，且有  

12、0; 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），K0    这就形成了一个基本的复杂性类。

13、此外可以定义与它相关的其他两个复杂性类PK和pk  如下：     PK=Co-Pk=L  *|LPk      pO= P，Pk+1=p（Pk），K0    这三种复杂性类有下述基本关系：    pK      PkPK，PkPK       Pk+1    由此可见，  &#

14、160;  Pk     PkPK=pK       K0       K0       K0    由Pk，PK及Pk (k0)所描述的层次结构记为PH，即多项式谱系。    卡普给出了多项式谱系的基本思想后，由迈耶(AMeyer)和斯托克迈耶(LStockmeyer)在1973年给出了严格形式化定义，拉特

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

16、情请参阅计算机研究与发展，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 AFrenkel)的采访，演说全文和采访时的对话刊载于Communications ofACM