PC 2018 - Workshop on Proof Complexity (PC 2018)

Proof complexity focuses on the complexity of theorem proving procedures. The central question in proof complexity is: given a theorem F (e.g., a propositional tautology) and a proof system P (i.e., a formalism usually comprised of axioms and rules), what is the size of the smallest proof of F in the system P? Moreover, how difficult is it to construct a small proof? Many ingenious techniques have been developed to try to answer these questions; and they bare tight relations to intricate theoretical questions from computational complexity (such as the celebrated P vs. NP problem), first-order arithmetic theories (e.g. separating theories of bounded arithmetic) as well as to practical problems in SAT solving.