图灵奖：史蒂芬·库克（1982）

图灵奖是计算机界最负盛名的奖项，有“计算机界诺贝尔奖”之称。”图灵奖”系列将介绍历届获奖者。每周二更新，本文为第 20 期。图灵奖：史蒂芬·库克（1982）

文章来自微信公众号“科文路”，欢迎关注、互动。转发须注明出处。

本文来自 wiki:Stephen Cook，翻译基于 谷歌翻译.

P=NP？

史蒂芬·库克（生于 1939 年 12 月 14 日）是一位美籍加拿大计算机科学家和数学家，在复杂性理论（complexity theory）和证明复杂性（proof complexity）领域做出了重大贡献。他现在是多伦多大学计算机科学系和数学系的大学教授。

他于 1982 年获得图灵奖。

其图灵奖颁奖词为“表彰他以重大而深刻的方式增进了我们对计算复杂性的理解。他在 1971 年 ACM SIGACT 计算理论研讨会上发表的开创性论文“定理证明过程的复杂性”为 NP 完备性理论奠定了基础。随后对 NP 完全类问题的边界和性质的探索是过去十年中计算机科学中最活跃和最重要的研究活动之一”。（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.）

生平

库克于 1961 年在密歇根大学获得学士学位，并分别于 1962 年和 1966 年在哈佛大学数学系获得硕士和博士学位。

他于 1966 年加入加州大学伯克利分校数学系，担任助理教授，直到 1970 年他拒绝了续聘。

在庆祝伯克利电气工程和计算机科学系成立 30 周年的演讲中，图灵奖得主、伯克利教授理查德·卡普 (Richard Karp) 表示：“我们无法说服数学系给予他终身教职，这是我们永远的耻辱。 ”

库克于 1970 年加入多伦多大学计算机科学和数学系，担任副教授，并于 1975 年晋升为教授，于 1985 年晋升为杰出教授。

P/NP 问题

在攻读博士学位期间，库克研究了函数的复杂性，尤其是乘法。

在他 1971 年的开创性论文“定理证明程序的复杂性”（The Complexity of Theorem Proving Procedures）中，库克形式化了多项式时间归约（也称为库克归约）和 NP 完备性的概念，并通过证明布尔可满足性问题（通常称为 SAT）是 NP 完全的来证明了 NP 完全问题的存在性。该定理同时由苏联的列昂尼德·莱文（Leonid Levin）独立证明，因此被命名为库克-莱文定理。

这篇论文还阐述了计算机科学中最著名的问题，即 P/NP 问题（P versus NP problem）。通俗地说，P/NP 问题询问每个优化问题的答案是否可以通过有效的算法验证正确性/最优性。鉴于日常生活中存在大量此类优化问题，对P/NP问题的积极回答可能会产生深远的实践、哲学结论。

库克猜想，存在优化问题（具有易于检查的解决方案）无法通过有效的算法解决，即 P 不等于 NP。

这一猜想引发了计算复杂性理论的大量研究，极大地提高了我们对计算问题的固有难度以及可以有效计算的内容的理解。然而，这个猜想仍然存在，并且是七个著名的千禧年问题之一。

贡献

• NP-completeness
• Propositional proof complexity
• complexity theory

~~

都看到这儿了，不如关注每日推送的“科文路”、互动起来~

至少点个赞再走吧~

觉得还不错？可以在公众号菜单栏找到“赞赏”入口~