Skip to content



Basic proof complexity III

Krajicek, J (Prague)
Tuesday 14 March 2006, 11:00-12:00

Seminar Room 1, Newton Institute


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

Back to top ∧