FLoC2010 Logo

Propositional Proof Complexity: Theory and Practice

Workshop affiliated with the Federated Logic Conference (FLoC 2010)/ SAT 2010

Edinburgh, July 9, 2010

The PPC workshop is combined with the 11th International Workshop on Logic and Computational Complexity.

Propositional proof complexity is an area of mathematics (theoretical computer science) within the intersection of mathematical logic and computational complexity and is centered around the question whether the complexity class NP is closed under complementation. It is tightly connected with other areas like computational complexity theory, automated theorem proving and cryptography.

The purpose of the workshop is to bring together researchers in various parts of mathematics and computer science interested in propositional proof complexity. The topic of the workshop will be on propositional proof theory with connections to issues of complexity in the widest sense. Our aim is to expose, through invited and contributed talks, current developments in proof complexity that are most relevant to SAT-solving and automated theorem proving.


The topics of the workshop will be on propositional proof complexity in the widest sense with connections to applications for which complexity issues are essential and include (but are not restricted to):
  • Proof complexity of propositional proof systems: resolution, Frege systems, Nullstellensatz proofs etc.
  • Complexity measures for proofs
  • Automatizability of propositional proof systems
  • Monotone circuit complexity in relation to propositional proof complexity
  • Complexity of proof transformations
  • Algorithmic applications of proof complexity theory
  • Applications of games to propositional proof complexity

Invited Speakers

Stephen A. Cook, University of Toronto, Canada
Nicola Galesi, Universita di Roma, Italy

Important Dates

  • Paper submission deadline (EXTENDED): 06.04.2010
  • Notification of acceptance: Beginning of May 2010
  • Final papers due: 07.05.2010
  • FLoC early registration deadline: tba
  • Workshop: July 9, 2010