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.

Skip to content

LAA

Seminar

Basic proof complexity I

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

Seminar Room 1, Newton Institute

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

[pdf ]

Back to top ∧