1982 史提芬·古克

shiyi18

Stephen A Cook

PHOTOGRAPHS
BIRTH:
1939, Buffalo NY

EDUCATION:
B.Sc., University of Michigan (1961); S.M., Harvard University (1962); Ph.D., Harvard University (1966).

EXPERIENCE:
Assistant Professor, University of California, Berkeley (1966-1970); Associate Professor, University of Toronto (1970-1975); Professor, University of Toronto (1975-1985); University Professor, University of Toronto (from 1985).

HONORS AND AWARDS:
NSERC E.W.R. Steacie Memorial Fellowship (1977); Association for Computer Machinery Turing Award (1982); Canada Council Killam Research Fellowship (1982); Canada Council Izaak Walton Killam Memorial Prize (1997); CRM-Fields Prize (1999); Royal Society of Canada John L. Synge Award (2006); NSERC Award of Excellence (2007); Czech Academy of Sciences Bernard Bolzano Medal (2008); Fellow, Royal Society of Canada; Fellow, Royal Society of London; Fellow, Association for Computing Machinery; Member, National Academy of Sciences (U.S.); Member, American Academy of Arts and Sciences; Member, Gottingen Academy of Sciences; Gerhard Herzberg Canada Gold Medal for Science and Engineering (2013) which comes with $1 million in research funding; the Government of Ontario appointed him to the Order of Ontario in 2013, the highest honor in Ontario.



STEPHEN ARTHUR COOK DL Author Profile link
Canada – 1982
CITATION
For his advancement of our understanding of the complexity of computation in a significant and profound way. His seminal paper, "The Complexity of Theorem Proving Procedures," presented at the 1971 ACM SIGACT Symposium on the Theory of Computing, laid the foundations for the theory of NP-Completeness. The ensuing exploration of the boundaries and nature of NP-complete class of problems has been one of the most active and important research activities in computer science for the last decade.

SHORT ANNOTATED
BIBLIOGRAPHY
ACM TURING AWARD
LECTURE
RESEARCH
SUBJECTS
ADDITIONAL
MATERIALS
VIDEO INTERVIEW
Stephen Arthur Cook was born on December 14, 1939 in Buffalo, NY. Cook’s father worked as a chemist for a subsidiary of Union Carbide, and was also an adjunct professor at SUNY Buffalo. His mother worked as a homemaker and also as an occasional English teacher at Erie Community College. When he was ten, Cook moved with his family to Clarence, NY, which was the home of Wilson Greatbatch, the inventor of the implantable pacemaker. As a teenager, Stephen developed an interest in electronics and worked forGreatcatch, who was then experimenting with transistor-based circuitry.

Cook entered the University of Michigan in 1957, majoring in science engineering. He was introduced to computer programming in a freshman course taught by Bernard Galler. With a fellow student he wrote a program to test Goldbach’s conjecture that every even integer greater than two is the sum of two primes. Stephen eventually changed his major to mathematics, and received his Bachelor’s degree in 1961. He subsequently entered graduate studies in the Mathematics Department at Harvard University, where he encountered influences that would shape the direction of his future research, including Michael Rabin’s early work on computational complexity, Alan Cobham’s characterization of polynomial time computable functions, and his supervisor Hao Wang’s investigations in automated theorem proving. Cook received his Ph.D. in 1966. His thesis, titled On the Minimum Computation time of Functions, addresses the intrinsic computational complexity of multiplication. One contribution of the thesis was an improvement of Andrei Toom’s multiplication algorithm, which is now known as Toom-Cook multiplication. This algorithm is still a subject of study and is of practical importance in high-precision arithmetic.

Cook discusses his first exposure, around 1963, to complexity theory and his thesis work on the complexity of multiplication.       
After graduating, he joined the Mathematics Department at the University of California, Berkeley, leaving there in 1970 to take the position of Associate Professor in Computer Science at the University of Toronto. A year later, Cook presented his seminal paper, “The complexity of theorem proving procedures,” at the 3rd Annual ACM Symposium on Theory of Computing [1]. This paper marked the introduction of the theory of NP-completeness, which henceforth occupied a central place in theoretical computer science. (Leonid Levin independently introduced NP-completeness in 1973.) It was also an early contribution to the theory of propositional proof complexity, an area in which Cook continued to do extensive research over the next 40 years.

The theory of NP-completeness provides a way to characterize the difficulty of computational problems with respect to the time, that is, the maximum number of computational steps required to solve a problem, as a function of input size. Cook’s paper addresses the fact that many problems which are difficult to solve in this sense have solutions which are easy to verify once they are found. In current terminology, problems which are easy to solve comprise the class P, while those which are easy to verify comprise the class NP. Cook showed that certain problems in NP, now known as NP-complete problems, are as hard to solve as any others in NP, in the sense that if any one of these problems is easy to solve, then all problems in NP are easy to solve. Cook’s paper also was the source of the celebrated and still unsolved P versus NP question, which asks whether there are indeed problems in NP which are not in P, that is, problems whose solutions are easily verified but are not easily solved. A simple example which elucidates the relationship between the classes P and NP is the popular Sudoku puzzle (see here).

Cook explains why the question of whether P=NP is so important.       
Cook’s paper had an immediate impact. In 1972 Richard Karp published a paper in which he showed that twenty-one problems in combinatorics, optimization and graph theory which were believed to be computationally difficult were indeed NP-complete. Seven years later, Michael Garey and David Johnson published the book Computers and Intractability: A Guide to the Theory of NP-Completeness, which included a compendium of over three hundred problems which by then had been shown to be NP-compete. It would be hard to estimate how many problems have now been proved to be NP-complete, but they certainly number in the thousands. More significantly, the use of NP-completeness as a tool to understand computational difficulty spans virtually all areas of computer science.

The 1970 paper (“The complexity of theorem proving procedures”) introduced concepts and techniques which have had a lasting impact in various fields of computer science. In the paper, Cook introduces a canonical NP-complete problem, the satisfiability problem for Boolean formulas (SAT). The study of the SAT problem has become a field in its own right, and the development and use of specialized programs known as SAT-solvers has become an important practical approach to problems in areas such as verification and circuit design. In order to show that other problems are NP-complete, Cook developed the method of resource-bounded reducibility. This technique is an essential tool in computational complexity theory and is the foundation of complexity-based approaches to cryptographic security.

Cook discusses the creation and reception of his classic 1971 paper “The Complexity of Theorem-Proving Procedures”.       
The impact of the P versus NP problem has extended beyond the field of computer science. In particular, it has been recognized as a mathematical problem of fundamental significance. In the year 2000, Fields Medalist Steve Smale listed the P versus NP problem as the third in his list of eighteen unsolved problems in mathematics for the 21st century. In the same year, the Clay Mathematics Institute announced the Millennium Prize Problems. In the words of the Institute, the prize was proposed “to record some of the most difficult problems with which mathematicians were grappling at the turn of the second millennium.’’ The P versus NP was included as one of these seven fundamental problems.

Cook explains his belief that P does not equal NP.       
Cook has also made important contributions to areas of mathematical logic related to computational complexity. The paper “The relative efficiency of propositional proof systems,”[2] co-authored with his student Robert Reckhow, laid the foundations of propositional proof complexity. His 1975 paper, ``Feasibly constructive proofs and the propositional calculus’’ [3] introduces a logical system which characterizes feasible reasoning, and demonstrates how such reasoning is related to efficiency in propositional proof systems. He has also done significant work in areas including automata theory, parallel computation, program language semantics and verification, computational algebra, and computability and complexity in higher types.

Professor Cook’s work has received extensive recognition. He was awarded the ACM Turing Award in 1982. He is a fellow of the Royal Society of Canada and the Royal Society of London, and is a member of the National Academy of Sciences (U.S.), the American Academy of Arts and Sciences, and the Gottingen Academy of Sciences. He has been a recipient of the Canada Council Izaak Walton Killam Memorial Prize in 1997, the CRM-Fields Prize in 1999, the Royal Society of Canada John L. Synge Award in 2006, the NSERC Award of Excellence in 2007, and the Czech Academy of Sciences Bernard Bolzano Medal in2008. He was an NSERC Steacie Fellow in 1978-79 and was awarded a Killam Research Fellowship in 1982-83.

In 1985, Stephen Cook was promoted to the position of University Professor at the University of Toronto, and now holds the position of Distinguished University Professor in the Computer Science and Mathematics Departments. Over the course of his career he has mentored over thirty Ph.D. students, and continues to be active in teaching, research and graduate supervision. His book, Logical Foundations of Proof Complexity, co-authored with Phuong Nguyen, appeared in 2010. He currently lives in Toronto with his wife Linda, and has two sons. He is an avid sailor and a long-time member of the Royal Canadian Yacht Club.

Enduring Links of Interest

• Clay Foundation Millenium Problem Prize page on the P vs NP problem
• Oral history interview with Stephen A. Cook at the Charles Babbage Institute
• Stephen A. Cook at the Mathematics Genealogy Project


Author: Bruce Kapron



斯蒂芬-A-库克

照片
出生地：美国
1939年，纽约州水牛城

教育：密歇根大学理科学士（1961年）；哈佛大学硕士（1962年）；哈佛大学博士。
密歇根大学理学士（1961年）；哈佛大学理学硕士（1962年）；哈佛大学博士（1966年）。

工作经历
加州大学伯克利分校助理教授（1966-1970）；多伦多大学副教授（1970-1975）；多伦多大学教授（1975-1985）；多伦多大学教授（1985年起）。

获得的荣誉和奖项。
NSERC E.W.R. Steacie纪念奖学金（1977）；计算机协会图灵奖（1982）；加拿大理事会Killam研究奖学金（1982）；加拿大理事会Izaak Walton Killam纪念奖（1997）；CRM-Fields奖（1999）；加拿大皇家学会John L．Synge奖（2006年）；NSERC优秀奖（2007年）；捷克科学院Bernard Bolzano奖章（2008年）；加拿大皇家学会会员；伦敦皇家学会会员；计算机械协会会员；美国国家科学院会员。 美国国家科学院院士；美国艺术与科学院院士；哥廷根科学院院士；格哈德-赫兹伯格加拿大科学与工程金奖（2013年），附带100万美元的研究经费；安大略省政府于2013年任命他为安大略省最高荣誉勋章。



STEPHEN ARTHUR COOK DL作者简介链接
加拿大 - 1982年
嘉奖
因为他以重大而深刻的方式推动了我们对计算复杂性的理解。他在1971年ACM SIGACT计算理论研讨会上发表的开创性论文 "The Complexity of Theorem Proving Procedures"，为NP-Completeness的理论奠定了基础。随后对NP-完全性类问题的边界和性质的探索，是过去十年计算机科学中最活跃和最重要的研究活动之一。

简短注释
书目
亚马逊图灵奖
讲座
研究
主题
额外的
材料
视频采访
斯蒂芬-阿瑟-库克于1939年12月14日出生在纽约州的水牛城。库克的父亲在联合碳化物公司的一个子公司担任化学家，同时也是纽约州立大学水牛城分校的兼职教授。他的母亲是一名家庭主妇，也是伊利社区学院的一名临时英语教师。当他10岁时，库克与他的家人搬到了纽约州克拉伦斯，那里是植入式心脏起搏器的发明者威尔逊-格雷巴奇的家。十几岁时，斯蒂芬对电子学产生了兴趣，并为当时正在进行基于晶体管的电路实验的格雷巴奇工作。

库克于1957年进入密歇根大学，主修科学工程。他在伯纳德-盖勒教授的大一课程中开始接触计算机编程。他和一个同学写了一个程序来测试哥德巴赫的猜想，即每一个大于2的偶数都是两个素数之和。斯蒂芬最终将他的专业改为数学，并于1961年获得学士学位。他随后进入哈佛大学数学系读研究生，在那里他遇到了影响他未来研究方向的因素，包括迈克尔-拉宾关于计算复杂性的早期工作，艾伦-科巴姆关于多项式时间可计算函数的特征，以及他的导师王浩关于自动定理证明的研究。库克于1966年获得博士学位。他的论文题为《论函数的最小计算时间》，探讨了乘法的内在计算复杂性。该论文的一个贡献是对安德烈-图姆的乘法算法的改进，该算法现在被称为图姆-库克乘法。这个算法仍然是一个研究对象，在高精度算术中具有实际的重要性。

库克讨论了他在1963年左右第一次接触到复杂性理论以及他关于乘法复杂性的论文工作。       
毕业后，他加入了加州大学伯克利分校的数学系，1970年离开那里，在多伦多大学担任计算机科学副教授的职位。一年后，库克在第三届ACM计算理论年度研讨会上发表了他的开创性论文《定理证明程序的复杂性》[1]。这篇论文标志着NP完备性理论的引入，此后它在理论计算机科学中占据了核心地位。(Leonid Levin在1973年独立地提出了NP-completeness。)这也是对命题证明复杂性理论的早期贡献，在接下来的40年里，库克继续在这个领域进行广泛的研究。

NP完备性理论提供了一种方法来描述计算问题在时间方面的难度，也就是说，解决一个问题所需的最大计算步骤数，是输入大小的函数。库克的论文论述了这样一个事实：许多在这个意义上难以解决的问题，其解决方案一旦被找到就很容易验证。在目前的术语中，容易解决的问题包括P类，而那些容易验证的问题则包括NP类。库克表明，NP中的某些问题，现在被称为NP-complete问题，与NP中的任何其他问题一样难以解决，也就是说，如果这些问题中的任何一个容易解决，那么NP中的所有问题都容易解决。库克的论文也是著名的但仍未解决的P与NP问题的来源，该问题问的是NP中是否确实存在不在P中的问题，也就是说，其解决方案容易验证，但不容易解决的问题。阐明P类和NP类之间关系的一个简单例子是流行的数独谜题（见这里）。

库克解释了为什么P=NP的问题如此重要。       
库克的论文立即产生了影响。1972年，理查德-卡普（Richard Karp）发表了一篇论文，表明组合学、优化和图论中被认为在计算上很困难的21个问题确实是NP-完全。七年后，迈克尔-加里和大卫-约翰逊出版了《计算机与难解性》一书。该书包括三百多个当时已被证明是NP-compete的问题的汇编。很难估计现在有多少问题被证明是NP-完备的，但它们肯定是数以千计的。更重要的是，使用NP完备性作为理解计算难度的工具，几乎跨越了计算机科学的所有领域。

1970年的论文（"定理证明程序的复杂性"）引入了一些概念和技术，对计算机科学的各个领域都产生了持久的影响。在这篇论文中，库克介绍了一个典型的NP-complete问题，即布尔公式的可满足性问题（SAT）。对SAT问题的研究本身已经成为一个领域，开发和使用被称为SAT求解器的专门程序已经成为解决验证和电路设计等领域问题的重要实践方法。为了证明其他问题是NP-完备的，库克开发了资源有界的还原性方法。这一技术是计算复杂性理论中的一个重要工具，是基于复杂性的加密安全方法的基础。

库克讨论了他在1971年发表的经典论文《定理证明程序的复杂性》的创作和接受情况。       
P与NP问题的影响已经延伸到计算机科学领域之外。特别是，它已被认为是一个具有根本意义的数学问题。2000年，菲尔兹奖得主史蒂夫-斯麦尔（Steve Smale）将P与NP问题列为21世纪数学领域18个未解决的问题中的第三个。同年，克莱数学研究所宣布了千年奖问题。用研究所的话说，这个奖项是为了 "记录数学家们在第二个千年之交正在努力解决的一些最困难的问题"。P与NP的对比被列为这七个基本问题之一。

库克解释了他的信念：P不等于NP。       
库克还对与计算复杂性有关的数理逻辑领域做出了重要贡献。与他的学生Robert Reckhow合写的论文《命题证明系统的相对效率》[2]，奠定了命题证明复杂性的基础。他1975年的论文 "可行的构造证明和命题微积分"[3]介绍了一个逻辑系统，该系统表征了可行的推理，并证明了这种推理与命题证明系统的效率的关系。他还在自动机理论、并行计算、程序语言语义学和验证、计算代数以及高等类型的可计算性和复杂性等领域做了大量工作。

库克教授的工作得到了广泛的认可。他于1982年被授予ACM图灵奖。他是加拿大皇家学会和伦敦皇家学会的研究员，也是美国国家科学院、美国艺术与科学学院和哥廷根科学院的成员。他是1997年加拿大委员会Izaak Walton Killam纪念奖、1999年CRM-Fields奖、2006年加拿大皇家学会John L. Synge奖、2007年NSERC优秀奖和2008年捷克科学院Bernard Bolzano奖的获得者。1978-79年，他是NSERC的Steacie研究员，1982-83年被授予Killam研究奖学金。

1985年，斯蒂芬-库克被提升为多伦多大学的大学教授，现在担任计算机科学和数学系的杰出大学教授的职务。在他的职业生涯中，他已经指导了三十多名博士生，并继续积极从事教学、研究和研究生指导工作。他与Phuong Nguyen合写的《证明复杂性的逻辑基础》一书于2010年出版。他目前与他的妻子琳达住在多伦多，有两个儿子。他是一个狂热的水手，是加拿大皇家游艇俱乐部的长期会员。

持久关注的链接

- 克莱基金会千年问题奖关于P与NP问题的页面
- 查尔斯-巴贝奇研究所对斯蒂芬-A-库克的口述历史访谈
- 史蒂芬-A-库克在数学家谱项目中的介绍


作者。Bruce Kapron