Eastern Great Lakes Theory Workshop Talk

Proof Complexity and Computational Complexity

Stephen Cook, University of Toronto

Saturday, September 6, 1:30 pm- 2:30pm

ABSTRACT

We study the computational complexity of the concepts which need to be defined in order to prove theorems of interest in computer science. This has applications both to propositional proof complexity, where we are interested in determining which tautology families have polynomial size proofs in various proof systems, and in bounded arithmetic, where we study the strength of weak theories of arithmetic needed to prove the theorems of interest.

Slides

Speaker Bio

Stephen A. 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 author of many 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. He was awarded a Steacie Fellowship in 1977,a Killam Research Fellowship in 1982, and received the CRM/Fields Institute Prize in 1999. 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-eight students have completed their PhD degrees under his supervision.

< Schedule < EaGL homepage