skip to content

Capturing complexity classes by their reasoning power

Presented by: 
S Cook [Toronto]
Tuesday 11th April 2006 - 09:30 to 10:30
INI Seminar Room 1

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.

University of Cambridge Research Councils UK
    Clay Mathematics Institute London Mathematical Society NM Rothschild and Sons