AAAI Conference 2008 Conference Paper
Clause Learning Can Effectively P-Simulate General Propositional Resolution
- Philipp Hertel
- Toniann Pitassi
Currently, the most effective complete SAT solvers are based on the DPLL algorithm augmented by clause learning. These solvers can handle many real-world problems from application areas like verification, diagnosis, planning, and design. Without clause learning, however, DPLL loses most of its effectiveness on real world problems. Recently there has been some work on obtaining a deeper understanding of the technique of clause learning. In this paper we utilize the idea of effective p-simulation, which is a new way of comparing clause learning with general resolution and other proof systems. We then show that pool proofs, a previously used characterization of clause learning, can effectively p-simulate general resolution. Furthermore, this result holds even for the more restrictive class of greedy, unit propagating, pool proofs, which more accurately characterize clause learning as it is used in practice. This result is surprising and indicates that clause learning is significantly more powerful than was previously known.