Towards NP-P via proof complexity and search

摘要

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.