Preprint:
Samuel R. Buss.
"Towards NP-P via Proof Complexity and Search."
Manuscript, 2009.
Download preliminary version: PDF.
Abstract: This is a survey of work on proof complexity and proof search, as motivated by the P versus NP problem. We discuss propositional proof complexity, Cook's program, proof automatizability, proof search, algorithms for satisfiability, and the state of the art of our (in)ability to separate P and NP.