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.