10-13 April 2006, New Directions in Proof Complexity, Isaac Newton Institute for Mathematical Sciences, Cambridge, UK

Proof complexity is an area of mathematics (and mathematical logic and computational complexity theory in particular) centered around the problem whether the complexity class NP is closed under complementation. With a suitable general definition of a propositional proof system (Cook and Reckhow 1979) this becomes a lengths-of-proofs question: Is there a propositional proof system in which every tautology admits a proof whose length is bounded above by a polynomial in the length of the tautology? The ultimate goal of proof complexity is to show that there is no such proof system; that is, to demonstrate superpolynomial lower bounds for all proof systems.

For more information, see http://www.newton.cam.ac.uk/programmes/LAA/laaw04.html