Propositional proof complexity

Abstract

Propositional proof complexity studies efficient provability of those statements that can be expressed in propositional logic, in various proof systems, and under various notions of “efficiency.” Proof systems and statements of interest come from a variety of sources that, besides logic and combinatorics, include many other areas like combinatorial optimization and practical SAT solving. This article is an expanded version of the ECM talk in which we will attempt to convey some basic ideas underlying this vibrant area.