The INI has a new website!

This is a legacy webpage. Please visit the new site to ensure you are seeing up to date information.

Skip to content



Capturing complexity classes by their reasoning power

Cook, S (Toronto)
Tuesday 11 April 2006, 09:30-10:30

Seminar Room 1, Newton Institute


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.


[pdf ] [ps  ]


MP3MP3 Real AudioReal Audio

Back to top ∧