峥嵘岁月 | 一个被伯克利炒鱿鱼的图灵奖得主

2017 年 9 月 16 日 德先生

前几天再次收到一个毕业十几年的学生的邮件，姑且叫他小C，内容是他写了50多页自称证明了P≠NP的证明。他告诉我他也把这个证明发给了几个领域内专家，包括最初问题的提出者，1982年的图灵奖得主，目前执教于加拿大多伦多大学的史提芬·库克（StephenA. Cook）。这让我想起了皇冠的设置者库克大师，今天我想分享下他的故事。

库克教授近照

按照中国人的习惯说法，库克应该算是出生在一个知识分子家庭。他的父亲是个化学家，密歇根大学的教授，他的母亲则在一家社区大学教英文。受父母影响，1957年库克高中毕业后选择上了密歇根大学，他的专业是科学工程。大一时，库克选修了许多门课程，而最让他痴迷的却是一周只有一个学时的计算机编程课程。他写的第一个程序就是验证每个中国数学爱好者都熟知的哥德巴赫猜想——任何一个大于2的偶数都可分解成两个质数之和。当然计算机在那会儿就像中国七十年代的彩色电视机，属于稀缺物品啊，计算机专业也没有自己地盘，基本隶属于数学系。所以，库克跑到了数学系。

本科毕业后，库克进入哈佛大学数学系。和许多读研读博的学生不一样，库克进入哈佛时，并没有选定任何教授。他只是对计算机感兴趣，一开始并没有明确的研究领域。艾伦·科巴姆（Alan Cobham）著名的“乘法比加法难吗？”问题，吸引了库克，从此古克开始进入了极其抽象的计算复杂度的研究领域。科巴姆1964年发表的内在函数复杂性的论文是对库克影响最大的两篇文章之一，库克在他自己的个人网站上一直把它列为具有历史意义的文献。

有意思的是，库克的博士论文导师是一个中国人王浩（Hao Wang）。王教授那时是哈佛应用物理的教授，库克上过他两门课，两人很投缘，非常谈得来。库克的博士论文是关于乘法复杂性的（论文名字是“关于函数最小计算时间– On the Minimum Computation Time of Functions”），这显然不是王教授的强项。但大家也就此可以看出库克这哥们儿的性格，喜欢你，你就做我的导师好了。至于是否能得到实际的帮助，库克这家伙完全不在乎，这完全是性情中人啊！

1966年库克博士毕业，他的第一份工作是担任加州大学伯克利分校数学系及计算机中心的助理教授（Assistant Professor），主要负责教授计算机逻辑和计算机编程课程。在伯克利校园里，库克度过了四年心无旁骛的时光，窗外事通通不理会，只专心其计算复杂性的研究。我的博士导师哈尔•萨德伯勒（Hal Sudborough）教授是库克的朋友，有次他告诉我，库克在伯克利的四年里因为没有在高大上的数学杂志上发表数量足够的论文，所以1970年，伯克利解除了和库克的合约，炒了库克同志的鱿鱼——当代最伟大的计算机理论大师。极具讽刺的是，一年后，库克发表了其P和NP关系的历史性论文，并因此在1982年获得了图灵奖。而最终在伯克利拿到终身教授的理查德·卡普（RichardKarp）教授，则因为论证了库克提出的NP完全问题的大量存在（他一口气证明了21个NP完全问题）于1985年获得了图灵奖。

2002年回忆被炒鱿鱼这件事时，库克说我的数学系同事不大看好我的研究，我平时也不大和他们来往，决定解除我合约的投票是终身教授的不记名投票，绝大部分人觉得我没有前途。

我一直认为美国大学的终身教授（Tenure）制度有很多弊端，年轻老师往往要看老教授的脸色，因为这些人能在很大程度上决定他们的命运。年轻老师的研究都是以尽量多发表论文为目的，只关注数量，而不是质量。因为许多大学都会明码标价，列出拿到终身教授最少需要的论文篇数。当然，美国大学也没有从库克教授的例子汲取应有的教训。

1970年，库克同时收到了耶鲁大学和加拿大多伦多大学的邀请，大多数人都会选择耶鲁。但因为更喜欢多伦多的环境，尤其是多大计算机系的氛围，库克选择了多大，再次证明库克性情中人啊！他的加盟，极大的拉动了多大计算机系的排名。

来到多大的第二年，也就是1971年，在 ACM的STOC （Symposiumon the Theory of Computing）会议上，库克教授作了题为 “定理证明过程复杂性 -The Complexity of Theorem Proving Procedure”的报告。我的导师也是听众之一，据他形容，库克报告完了以后，整个会议都沉浸在兴奋中，大家意识到这篇论文接触到了计算复杂性的核心，计算机理论的一个新时代开始了。顺便说一句，STOC会议是计算机的顶级会议之一，级别等同于华山论剑。

经历了46年之后，虽然众多计算机科学工作者（前面的小C也算一个）花了无数的精力，但仍未解开P和NP之谜。出生于1939年12月14日的库克教授，仍然在教授他喜爱的计算复杂度的课程。下面是他这学期和下学期教的两门课程：

Teaching Fall, 2017: CSC438F/2404F Computability and Logic

Taught Winter, 2017: CSC463H Computational Complexity andComputability

📚往期文章推荐