Preprint:
Samuel R. Buss.
"Towards NP-P via Proof Complexity and Search."
To appear.
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.