Samuel R. Buss.
"Towards NP-P via Proof Complexity and Search."
Annals of Pure and Applied Logic 163, 7 (2012) 906-917.
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.
Back to Sam Buss's publications page.