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: