The P vs NP Problem and its Place in Complexity Theory
Stephen Cook University of Toronto
Thursday, September 28, 2006 4:00 p.m. in 1800
Engineering Hall (reception following in 1413 Engineering Hall)
Abstract: The Clay Mathematics Institute offers a million dollars to anyone
solving the question of whether P equals NP. We discuss the importance
of the problem and explain why most complexity theorists believe
P unequal 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. The question of
whether NP equals coNP motivates the important field of propositional
proof complexity.
Speaker's Bio:
Stephen Cook was born in Buffalo, New York, received his BSc degree from
University of Michigan in 1961, and his S.M. and PhD degrees from Harvard
University in 1962 and 1966 respectively. From 1966 to 1970 he was Assistant
Professor, University of California, Berkeley. He joined the faculty at the
University of Toronto in 1970 as an Associate Professor, and was promoted to
Professor in 1975 and University Professor in 1985. His principal research
areas are computational complexity and proof complexity, with excursions
into programming language semantics and parallel computation.
He is the author of over 60 research papers, including his famous 1971 paper
"The Complexity of Theorem Proving Procedures" which introduced the theory of
NP completeness and proved that the Boolean satisfiability problem is NP
complete. He is the 1982 recipient of the Turing award, and was awarded a
Steacie Fellowship in 1977, a Killam Research Fellowship in 1982, and received
the CRM/Fields Institute Prize in 1999. He received Computer Science teaching
awards in 1989 and 1995. He is a fellow of the Royal Society of London,
Royal Society of Canada, and was elected to membership in the National
Academy of Sciences (United States) and the American Academy of Arts and
Sciences. Twenty-six students have completed their PhD degrees under his
supervision, and many of them now have prominent academic careers of their
own.
|