斯蒂芬·库克
--NP完全性理论的奠基人
【个人生平】
加拿大多伦多大学教授斯蒂芬·库克(Stephen Arthur Cook)因在计算复杂性理论方面的贡献，尤其是在奠定NP完全性理论基础上的突出贡献而荣获1982年度的图灵奖。
但库克实际上是美国科学家，1939年12月14日生于纽约州的布法罗(Buffalo)，他的父亲是一名化学家，在著名的联合碳化物公司工作，同时在布法罗大学任教，有一份不错的收入。但库克的父亲喜欢农村的恬静生活和清新空气，因此在库克10岁时全家迁居到纽约州克拉伦斯的一个奶牛场。在这里，少年库克可以与牛羊为伴，还学会了挤奶。在乡村中学，库克的数学成绩比较好，但那时他并没有梦想当数学家。库克的另一个爱好是下棋，这帮助他发展了逻辑思维能力。在克拉克伦斯，当时出现了一位传奇式的英雄，那就是威尔逊·格莱特巴郝(Wilson Greatbatch)，他发明了可植入式心脏起搏器，挽救了世界上无数人的性命，使他远近闻名。库克对这位发明家也很敬仰和崇拜，暑假时曾到他手下去打工，帮他焊晶体管电路板。当时晶体管问世不久，是新鲜事物，库克对神奇的晶体管也很有兴趣，想当个电气工程师。
1957年中学毕业后，库克离开克拉伦斯去上密歇根大学，专业是科学工程。一年级时他选了一门新开设的课程——程序设计，第一次接触计算机。作为作业，他编了一个Algol程序以验证哥德巴赫猜想，在机器允许的范围内，每个大于3的偶数都是2个素数之和。这使库克开始对计算机科学发生兴趣。
1961年库克获得学士学位以后，转入哈佛大学研究生院深造，第二年就取得了理科硕士学位。他接着攻读数学博士学位，原先的打算是研究代数学。然而这时他遇到了一些教师，对他产生了很大的影响，改变了他的兴趣和方向。首先是哈佛研究生院对新兴学科十分重视，虽然计算复杂性理论这一学科分支其时还处于萌芽与初创时期，它就邀请了这方面的一些先驱与奠基人，其中包括拉宾(M．Rabin，1976年图灵奖获得者)、哈特马尼斯(J．Hartmanis)和斯坦恩斯(R．Steams，这两人是1993年图灵奖获得者)等人前来讲学或作报告。库克对他们所研究和探索的问题产生了极大的兴趣，从而把自己的研究也定在了这个方向。他的博士论文“论乘法的最小计算时间”(On the Minimum Computation Time for Multiplication)就是他涉足这一领域的初步尝试。但这个课题局跟性太大，无法从中找出一般规律。这时，在哈佛大学应用科学研究所任教的美籍华人学者王浩的研究工作引起了库克的注意和启发了他。王浩是国际知名的数理逻辑专家和计算机科学家，他曾对图灵的计算理论进行深入研究并提出了图灵机的一种变形叫B机器(Bmachine)。B机器的特点是总共只有4条指令，机器不能自我修改，即不能抹去带上的记号。B机器比图灵机更加接近于实际机器，它能计算的函数正好是部分递归函数。当时王浩正致力于研究自动定理证明，即由计算机自己去证明定理，具体而言是证明谓词演算中的定理，这就涉及到可满足性问题(Satisfiable)，即是否存在一个真假值的赋值，使得给定的公式成立。如果存在，那么就称这个公式是可满足的，否则就是不可满足的。一般谓词演算公式的可满足性问题，图灵早就解决了，他指出，甚至在无限的时间里，要想确定谓词演算中的某个公式是否可满足，在计算上都是不可能的。因此，王浩是从复杂性的角度去研究谓词演算的可满足性的。
王浩的研究工作给了库克以极大的启发，他认识到，自动定理证明可以作为研究计算复杂性问题的一个很好的突破口。但是由于谓词演算涉及个体与群体，公式中包含所谓量词(quantifier)，即全称量词d1(universal quantifier，用“∨”表示)和存在量词exists(existential quantifier，用“∧”表示)，使研究变得复杂而困难。因此库克改从比较单纯和简单的命题演算公式的自动证明人手研究计算复杂性，果然获得成功。
1971年5月，他在ACM于俄亥俄州的Shaker Heights举行的第三届计算理论研讨会上发表了那篇著名的论文：“定理证明过程的复杂性”(The Complexity of Theorem Proving Procedures)，在这篇论文中，库克首次明确提出了NP完全性问题，并奠定了NP完全性理论的基础。所谓“NP完全性”(NP-completeness)问题是这样一个问题：由于P二?NP问题难以解决，库克就另辟途径，从NP类的问题中分出复杂性最高的一个子类，把它叫做NP完全类。库克证明，任取NP类中的一个问题，再任取NP完全类中的一个问题，则一定存在一个确定性图灵机上的具有多项式时间复杂性的算法，可以把前者转变成后者。这就表明，只要能证明NP完全类中有一个问题是属于P类的，也就证明了NP类中的所有问题都是P类的，即证明了P=NP。库克的这一研究成果为研究P=?NP的科学家们指明了一条捷径和一个方向，不必再像大海捞针似地去盲目探索了。虽然科学家们沿着库克指明的这条“捷径”仍在艰难地前进，至今没有达到光辉的终点(P=?NP的问题至今仍未有结论)，但学术界公认库克的NP完全性理论是对计算复杂性理论的一个重大贡献。库克的论文只证明了命题演算的可满足性问题是NP完全的，但在它的启发下，卡普(R．Karp，1985年图灵奖获得者)在第二年就证明了21个有关组合优化的问题也是NP完全的，从而加强与发展了NP完全性理论。
在1998年加盟苹果电脑担任全球业务高级副总裁之前，Cook 先生曾任康柏 (Compaq) 企业材料副总裁，负责采购、管理康柏的产品存货。在这之前，Cook 先生是Intelligent Electronics 经销商部门的首席运营官。Cook 先生还曾在 IBM 供职12年之久，他在 IBM 最近的职务为北美业务执行主管，负责 IBM 的 Personal Computer Company 在北美和拉美的制造和分销运作。
【个人成就】
库克在建立NP完全性理论时，为研究复杂性类之间的关系提出的方法，叫“复杂性归约”(complexity reduction)，用以比较问题的计算难度。库克所用的归约方法是多项式时间图灵归约，有时直接把它叫做库克归约。其要点如下：假设所考虑的问题都已编码成字母表∑上的语言(实例的集合)。设Ll、L2是∑上的两个语言，若存在以上：为oracle集的多项式时间图灵机M，其接受的语言为Ll，则称L1，多项式时间图灵归约到L2，记为i1≤PTL2。这时，对x是否属于L1的判别可转化为至多，|x|的多项式个元素是否属于i2的判别，因此L2∈p便导致L1∈p。从这种相对的意义上说，i1的计算不比L2难。≤；可以是定义在任何语言类D上的一种二元前序关系，如果存在L∈D，对于任何L'∈D，都有L'≤PtL，则L就是D中(在多项式时间图灵归约下)“最困难的”，称其为D-T完全的。
在库克归约的基础上，其他计算机科学家又用其他各种计算模型定义了其他一些复杂性归约，如多一归约、对数空间归约、Y-归约、随机归约和真值表归约等。但库克归约仍然是最常用的归约方法之一。复杂性归约除了用于判定向题外，还可以用于函数和搜索问题。
向库克颁发图灵奖的仪式是1982年10月25日在达拉斯举行的ACM年会上进行的。库克发表了题为“计算复杂性综述”(An Overview of Computational Complexity)的图灵奖演说，演说全面而系统地回顾了计算复杂性理论从萌芽到发展到成熟所走过的历程以及面临的新的挑战，还给出了上百篇有价值的参考文献，值得关心这一学科的人细细阅读。演说全文刊载于1983年6月的Communications of ACM，400-408页，也可见《前20年的ACM图灵奖演说集》(ACM Turing Award Lectures ——The First 20 Years：1966—1985，ACM h．411-432页。)