Six Feelings: 1982年的图灵奖获得者-Stephen Arthur Cook

Stephen Arthur Cook (1939--)

图灵奖获得时间：

1982年。第十七位图灵奖 (1982年) 获得者。

图灵奖引用 (Turing Award Citation) ：

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.

中文翻译：

( 授予 Stephen A. Cook 图灵奖以表彰其 ) 对我们深刻理解计算复杂性的开创性的贡献。Cook的开创性文章，1971年发表在ACM SIGACT Symposium on the Theory of Computing, "The Complexity of Theorem Proving Procedures", 揭开了计算复杂性中NP完全性的研究。在此基础上的关于NP完全性问题的本质和边界的研究与探讨成为过去十年来计算机科学最活跃和重要的研究领域之一。

编者注：

Cook著名的的NP完全性文章：

The Complexity of Theorem Proving Procedures

Cook在其研究文章中，提出并证明了后来以其名字命名的Cook's Theorem(Cook定理)。关于Cook定理，可参见：

http://en.wikipedia.org/wiki/Cook%27s_theorem

简单而言，Cook证明了SAT(Boolean Satisfiability Problem)问题是一个NP完全性问题。

关于NP完全性问题的定义通常是：

一个可判定性问题C是NP完全的，如果：

1。这个问题是NP问题。

2。所有其他的NP问题可以归约为C问题。

关于NP， P问题，特别是著名的P=NP？的著名难题，可参见：

http://en.wikipedia.org/wiki/Complexity_classes_P_and_NP

关于各种计算复杂性问题的关系图，可参阅：

http://en.wikipedia.org/wiki/Complexity_class

P是否等价与NP的问题已经成为数学界，计算理论界的一个著名的难题。不管是谁能精确的证明P等价与NP，和P不等价与NP，他/她都可以获得百万美金的悬赏。(编者相信，他/她还会立刻得到图灵奖)。有兴趣的读者可参见：

http://www.claymath.org/millennium/

关于计算复杂性的一些游戏和智力题：

http://www.ics.uci.edu/~eppstein/cgt/hard.html

NP完全问题的集锦：

http://en.wikipedia.org/wiki/List_of_NP-complete_problems

http://www.answers.com/topic/list-of-np-complete-problems

http://en.wikipedia.org/wiki/Karp%27s_21_NP-complete_problems

Turing Award Lecture(图灵奖演讲文章)：

An Overview of Computational Complexity. Commun. ACM 26(6): 400-408(1983)

Stephen A. Cook简 介 :

Stephen Arthur Cook于1939年出身在纽约水牛城(Beffalo, NY).

Stephen在1961年从University of Michigan (www.umich.edu ) 获得其学士学位，于1962年和1966年从哈佛大学分别获得其硕士与博士学位。1966年到1970年，Stephen在加州Berkeley分校担任助理教授职务。1970年，Stephen加盟多伦多大学(www.utoronto.ca )并工作直到现在。