Herbert H. Maass Professor, School of Mathematics
March 15, 2016
Proof systems pervade all areas of mathematics (often in disguise: e.g. Reidemeister moves is a sound and complete proof system for proving the equivalence of knots given by their diagrams). Proof complexity seeks to to understand the minimal *length* of proofs relative to the length of theorem proved, mainly for propositional proof systems. In this talk I plan to survey some of the main motivations and goals, results and challenges of proof complexity, as well as its connections with circuit complexity.