PC 2018: WORKSHOP ON PROOF COMPLEXITY 2018
PC 2018 Home Page

Overview

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.

The workshop is part of the Federated Logic Conference 2018 in Oxford, UK, affiliated with the SAT conference. There will be a joint session with the Workshop on Quantified Boolean Formulas and Beyond.

Call for Presentations

We welcome abstracts of 1-2 pages presented finished, ongoing or if clearly stated even recently published work on proof complexity. Particular topics of interest are:

  • Proof Complexity
  • Bounded Arithmetic
  • Relations to SAT solving
  • Relations to Computational Complexity

Important Dates

Call for papers announced February 15, 2018
Abstract submission deadline   
April 15, 2018
Notification of authors   May 15, 2018 
Workshop dates July 7-8, 2018

 

Organization

The program committee of PC 2018 is shown below.