06022773

j

06022773 Buss, Samuel R. Towards NP-P via proof complexity and search. Ann. Pure Appl. Logic 163, No. 7, 906-917 (2012). 2012 Elsevier Science B.V. (North-Holland), Amsterdam EN proof complexity proof search propositional logic satisfiability resolution

doi:10.1016/j.apal.2011.09.009

Summary: This is a survey of work on proof complexity and proof search from a logico-algorithmic viewpoint, 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$.