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

Question

如题所述

Answer 1

在对旅行推销员问题进行研究的过程中，卡普发现，无论对算法作何种重大的改进，也无论用何种更高效的新算法使旅行推销员能周游的城市数进一步增加（包括后来采用一种称为“多面体组合学”的方法把它转变为线性规划问题，从而使周游城市数超过300），解题所需的时间总是问题规模（在这里是城市数）的函数，且以指数方式增长。这引起卡普的深思，并促使他进入计算复杂性领域进行更深层次的研究。1967年，正好以色列学者、计算复杂性理论研究的先驱拉宾（M．Rabin，1976年图灵奖获得者）从希伯莱大学来到IBM公司的沃森研究中心作客座研究员，并且和卡普住在同一公寓大楼(卡普长期单身，直到1979年44岁才结婚成家），他们成了朋友，经常一起上下班，一起散步，拉宾在计算复杂性理论方面的深刻见解给了卡普很多启发。
1968年，卡普离开IBM到加州大学伯克利分校工作。这里是计算机科学理论的又一个研究中心，库克(S．Cook，1982年图灵奖获得者)、布卢姆(M．Blum，1995年图灵奖获得者)等一批知名学者当时都在那里，学术气氛十分浓厚。布卢姆是计算复杂性理论的主要奠基人之一，库克则于1971年最早提出“NP完全性”问题。在这样的环境下，卡普对计算复杂性问题的研究日益深入。