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.

An Isaac Newton Institute Workshop

New Directions in Proof Complexity

Capturing Complexity Classes by their Reasoning Power (joint work with Phuong Nguyen)

Author: S Cook (University of Toronto)

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.