Skip to content

LAA

Seminar

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

[pdf ] [ps  ]

Audio

MP3MP3 Real AudioReal Audio

Back to top ∧