Bridging the gap between easy generation and efficient verification of unsatisfiability proofs
- 1 September 2014
- journal article
- research article
- Published by Wiley in Software Testing, Verification and Reliability
- Vol. 24 (8) , 593-607
Abstract
SUMMARY: Several proof formats have been used to verify refutations produced by satisfiability (SAT) solvers. Existing formats are either costly to check or hard to implement. This paper presents a practical approach that facilitates checking of unsatisfiability results in a time similar to proof discovery by embedding clause deletion information into clausal proofs. By exploiting this information, the proof‐checking time is reduced by an order of magnitude on medium‐to‐hard benchmarks as compared to checking proofs using similar clausal formats. Proofs in a new format can be produced by making only minor changes to existing conflict‐driven clause‐learning solvers and their preprocessors, and the runtime overhead is negligible. This approach can easily be integrated into Glucose 2.1, the SAT 2012 challenge winner, and SatELite, a popular SAT‐problem preprocessor. Copyright © 2014 John Wiley & Sons, Ltd.Keywords
Funding Information
- Defense Advanced Research Projects Agency (N66001-10-2-4087)
This publication has 16 references indexed in Scilit:
- Mechanical Verification of SAT Refutations with Extended Resolution2013
- Producing and verifying extremely large propositional refutationsAnnals of Mathematics and Artificial Intelligence, 2012
- versat: A Verified Modern SAT Solver2012
- The Mechanical Verification of a DPLL-Based Satisfiability SolverElectronic Notes in Theoretical Computer Science, 2011
- Formal verification of a modern SAT solver by shallow embedding into Isabelle/HOLTheoretical Computer Science, 2010
- Formalization and Implementation of Modern SAT SolversJournal of Automated Reasoning, 2009
- Efficiently checking propositional refutations in HOL theorem proversJournal of Applied Logic, 2009
- Minimizing Learned Clauses2009
- Improved Conflict-Clause Minimization Leads to Improved Propositional Proof Traces2009
- A Computing Procedure for Quantification TheoryJournal of the ACM, 1960