Propositional Proof Complexity: Theory and Practice

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.

Topics

• 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

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