Propositional proof complexity

  • Alexander A. Razborov

    University of Chicago, United States of America; Russian Academy of Sciences, Moscow, Russia
Propositional proof complexity cover
Download Chapter PDF

This book chapter is published open access.


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.