Proceedings of the AAAI Conference on Artificial Intelligence · 2010 · 54 citations · 18 references
ComputingComputer ScienceAlgorithmsKnowledge RepresentationTheory Of ComputationAutomated ReasoningConstraint SatisfactionDeductive ReasoningProof AssistantsTheorem ProvingAlgorithmic Lower BoundsBoolean Satisfiability ProblemComplexity Of SatisfiabilityLower BoundsProof SystemsResolutions
Modern complete SAT solvers almost uniformly implement variations of the clause learning framework introduced by Grasp and Chaff. The success of these solvers has been theoretically explained by showing that the clause learning framework is an implementation of a proof system which is as poweful as resolution. However, exponential lower bounds are known for resolution, which suggests that significant advances in SAT solving must come from implementations of more powerful proof systems. We present a clause learning SAT solver that uses extended resolution. It is based on a restriction of the application of the extension rule. This solver outperforms existing solvers on application instances from recent SAT competitions as well as on instances that are provably hard for resolution.
18
A machine program for theorem-proving
Martin Davis, George Logemann, Donald Loveland · Communications of the ACM · 1962 · 3.2K citations · Full text
Matthew W. Moskewicz, Conor Madigan, Ying Zhao et al. · 2001 · 2.9K citations
The intractability of resolution
Armin Haken · Theoretical Computer Science · 1985 · 829 citations