Universiteit van Amsterdam

Events

Institute for Logic, Language and Computation

Please note that this newsitem has been archived, and may contain outdated information or links.

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

Date: 10-13 April 2006
Location: 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

Please note that this newsitem has been archived, and may contain outdated information or links.