Abstractions in Satisfiability Solvers
263 views · Published 17 August 2016 · 1:07:01 · Indexed 19 October 2026
Channel: Microsoft Research · 2016 · Science & Technology
Modern satisfiability solvers combine an elegant algorithm with clever heuristics and efficient engineering to achieve extremely high performance. I will show that the Conflict Driven Clause Learning algorithm in modern solvers has a natural characterisation in the framework of abstract interpretation. In particular, SAT solvers operate on a strict abstraction of propositional logic. This is surprising because an imprecise abstraction is used to obtain precise results. Time permitting, I will discuss how one may derive verification algorithms from satisfiability algorithms. I assume no background in either SAT solving or abstract interpretation.