Validating SAT Refutations

156 views · Published 9 August 2016 · 42:11 · Indexed 4 November 2026

Channel: Microsoft Research · 2016 · Science & Technology

Watch on YouTube

We give an overview of our recent work on validating satisfiability refutations.  Satisfiability (SAT) solvers are used not only to find a solution for a Boolean formula, but also to make the claim that no solution exists.  If no solution is reported, a solver can emit a proof of unsatisfiability, or refutation, which can then be validated by an unsatisfiability proof checker.  Ideally, SAT refutations should be:  easy to emit, compact, checked efficiently, checked in a trusted way, and expressive.  Existing proof formats support at most two of these five properties.  We present a new clausal proof format, called DRUP, that uses clause deletion information and can be checked efficiently.

More from this channel