|  |
 |
|
| |
|
|
Stephen Cook, University of Toronto17 October 2003 at 12:30 pm |
The P vs NP Problem and its Place in Complexity Theory
Abstract:
The Clay Mathematics Institute offers a million dollars to anyone solving the question of whether P = NP. We discuss the importance of the problem and explain why most complexity theorists believe P not = NP, despite the dramatic success of programs solving huge instances of the satisfiability problem. We show how this question is related to other fundamental problems in complexity theory, including the entangled problems of whether NP has polynomial size circuits, and whether some problems are inherently easier to solve using a source of random bits. We spend some time presenting basic issues in the field of propositional proof complexity.
Biography:
Stephen Cook was born in Buffalo, New York. He received his BSc degree from the University of Michigan in 1961 and his MS and PhD degrees from Harvard University in 1962 and 1966 respectively. From 1966 to 1970 he was an Assistant Professor at the University of California, Berkeley. He joined the University of Toronto in 1970, where he currently holds the position of University Professor. His principal research area is computational complexity, with excursions into programming language semantics, parallel computation, and especially the interaction between logic and complexity theory.
Professor Cook is one of the "founding fathers" of computational complexity. His seminal 1971 paper, "The complexity of theorem proving procedures", introduced the theory of NP-completeness, and stated the "P vs. NP" problem. This problem has become one of the most important open questions in computer science. It is now recognized as one of the top three mathematical problems of the 21st century, with the Clay Mathematics Institute offering a one million-dollar prize for its solution.
Professor Cook was the 1982 recipient of the Turing award, the most prestigious award in computer science. He is also a recipient of a Steacie Fellowship in 1977, a Killam Research Fellowship in 1982, the Killam Prize in Engineering/Computer Science in 1997 and the CRM/Fields Institute Prize in 1999. He is a fellow of the Royal Society of Canada and was elected to membership in the National Academy of Sciences (United States) and the Academy of Arts and Sciences.
This lecture is followed by a reception at East Academic Annex, room 1100
Admission is FREE