skip to content
 

Basic proof complexity I

Date: 
Tuesday 7th March 2006 - 11:00 to 12:00
Venue: 
INI Seminar Room 1
Abstract: 

In four talks I plan to cover some basic, both classical as well as recent, concepts of proof complexity. An approximate outline is:

(1) Cook-Reckhow definition, lengths of proofs, link to the NP versus coNP problem. Polynomial simulation, optimal proof systems. An overview of known lower bounds.

(2) Theories being "uniform" proof systems. Translations of arithmetical proofs into propositional proofs. Interpretation of lower bounds as constructions of models of bounded arithmetic theories.

(3) Proof complexity of (propositional) resolution. The size-width tradeoff, feasible interpolation, infinitary characterizations of hard tautologies.

(4) Hard tautologies: combinatorial principles, consistency statements, proof complexity generators.

Related Links

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