Article:
Samuel R. Buss.
"Towards NP-P via Proof Complexity and Search."
Annals of Pure and Applied Logic
163, 7 (2012) 906-917.
DOI: dx.doi.org/10.1016/j.apal.2011.09.009
Also in:
Foundational Adventures: Essays in Honor of Harvey Friedman
Templeton Foundation, 2012, Article 13. To appear.
Download preprint 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.