Fall 2008 - Propositional Proof Complexity (236604)

Scribe notes and exercises [PDF]

Let F be a boolean formula. A statement of a the form "There exists an assignment that sets F to TRUE" has a short proof. Such a proof is simply an assignment that sets F to TRUE. The complimenting statement, which is of the form "All assignments set F to FALSE" seems much harder to prove. In this course we shall study the complexity of proving such universal statements and address the following questions:

**What is a proof?****How long can a proof be as a function of the length of the statement?****If a short proof exists, can we find it?****Are statements about computation hard to prove?****How does all this relate to the fundamental question of P vs. NP (and NP vs. coNP)?**

Links

- Three surveys of propositional proof complexity by Segerlind, by Beame and Pitassi, and by Toran.
- The width method [Ben-Sasson and Wigderson, Ben-Sasson thesis].
- Space vs. width [Atserias and Dalmau].