理查德·卡普——发明“分支界限法”的三栖学者

    理查德·卡普教授现在是美国加州大学伯克利分校计算机科学讲座教授，担任美国科学院会刊（PNAS）等多个国际著名刊物编委。还是美国科学院、美国工程院、美国艺术与科学院、欧洲科学院院士。在计算机科学领域的基础贡献曾获图灵奖、冯诺依曼奖、美国国家科学勋章、哈佛大学百年奖章等奖项。
    卡普于1935年1月3日出生于波士顿，自那时以来一直对各种各样的兴趣感兴趣。他在哈佛大学学习过文科。他于1955年获得文学学士学位，第二年获得了理学硕士学位。然后，他继续在哈佛大学计算机实验室学习并获得博士学位。1959年获得应用数学博士学位。
    卡普在IBM期间，主要是深入研究了与实际应用有密切联系的一系列数学问题，如路径问题、背包问题、覆盖问题、匹配问题、分区问题、调度问题等，取得了许多出色的成果。这些问题有一个共同的特点，即如果用图来表示问题，那么当图中增加一个结点时，需要考察的可能的解的数目就急剧增加，形成所谓“组合爆炸”（combinatorialexplosion），使计算机的计算工作量大大增加，到一定程度就根本无法实现。以路径问题中最著名的旅行推销员问题为例，在卡普以前，最好的结果是Rand公司的丹齐格（GeorgeBenardDantzig）、福格申（R．Fulkerson）和约翰逊（S．Johnson）用手工和计算机相结合的办法，求出了包含49个城市的旅行推销员的最佳路线。卡普和他的同事海尔特(M．Held)经过反复研究，终于提出了一种称为“分枝限界法”（branch—and—boundmethod）的新方法，用这种新方法实现的算法使旅行推销员能周游的城市数达到65个，从而打破了由Rand公司保持的记录。
    1968年，卡普离开IBM到加州大学伯克利分校工作。这里是计算机科学理论的又一个研究中心，库克(S．Cook，1982年图灵奖获得者)、布卢姆(M．Blum，1995年图灵奖获得者)等一批知名学者当时都在那里，学术气氛十分浓厚。布卢姆是计算复杂性理论的主要奠基人之一，库克则于1971年最早提出“NP完全性”问题。在这样的环境下，卡普对计算复杂性问题的研究日益深入。