### Capturing complexity classes by their reasoning power

Cook, S *(Toronto)*

Tuesday 11 April 2006, 09:30-10:30

Seminar Room 1, Newton Institute

#### Abstract

For each of many standard complexity classes within NP we associate a canonical set of universal and existential theorems which are those which can be proved using concepts in the class. In some cases we can also associate canonical proof systems in the quantified propositional calculus.

#### Presentation