PC 2014 ABSTRACTS: EDITOR'S PREFACE

This volume contains the papers presented at the FLoC Workshop on Proof Complexity held on July 11-12, 2014 in Vienna.

The programme includes 4 invited talks and 13 contributed papers, selected by the programme committee. 

Topics presented at the workshop included recent and ongoing work on Proof Complexity, Bounded Arithmetic, Relations to SAT solving and to Computational Complexity.

Proof complexity is the study of 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, which bare tight relations to intricate theoretical open problems from computational complexity (such as the celebrated P vs. NP problem), mathematical logic (e.g. separating theories of Bounded Arithmetic) as well as to practical problems in SAT solving.