Speaker: Stephen Cook
University of Toronto

Thursday, June 12, 2003
1:15pm - 2:15pm
Eucalyptus Point (Room B)

ABSTRACT

This is a survey talk using the title as a theme, and presenting proof systems for both the quantifier-free and the quantified propositional calculus. The Pudlak/Buss "Liar Game" is used as a general method for introducing proof systems based on complexity classes.

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 area is computational complexity, with excursions into programming language semantics, parallel computation, and especially the interaction between logic and complexity theory. He is author of over 50 research papers, including his famous 1971 paper "The Complexity of Theorem Proving Procedures" which introduced the theory of NP completeness. He is the 1982 recipient of the Turing award, and was awarded a Steacie Fellowship in 1977 and a Killam Research Fellowship in 1982. He received Computer Science teaching awards in 1989 and 1995. 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 American Academy of Arts and Sciences. Eighteen students have completed their PhD degrees under his supervision, and many of them now have prominent academic careers of their own.