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.


Back to Sam Buss's publications page.