Proofdoors and Efficiency of CDCL Solvers

Abstract

We propose a new parameter called proofdoor in an attempt to explain the efficiency of CDCL SAT solvers over a certain class of formulas derived from circuit (esp., arithmetic) verification applications. Informally, given an unsatisfiable CNF formula F over n variables, a proofdoor decomposition consists of a chunking of the clauses into A_1, ..., A_k together with a sequence of interpolants connecting these chunks. Intuitively, a proofdoor captures the idea that an unsatisfiable formula can be refuted by reasoning chunk by chunk, while maintaining only a summary of the information (i.e., interpolants) gained so far for subsequent reasoning steps. We prove several theorems in support of the proposition that proofdoors can explain the efficiency of CDCL solvers for some class of circuit verification problems. First, we show that formulas with small proofdoors (i.e., where each interpolant is O(n) sized, each chunk A_i has small pathwidth, and each interpolant clause has at most O(log n) backward dependency on the previous interpolant) have short resolution (Res) proofs, and a certain configuration of CDCL solvers can compute such proofs in time polynomial in n. Second, we show that commutativity (miter) formulas over floating-point addition have small proofdoors and hence short Res proofs, even though they have large pathwidth. Third, we identify limits of the proofdoor framework: we show that a poor decomposition of arithmetic miter instances can force exponentially large interpolants, and hence our framework derives exponentially large Res refutations from such a decomposition, even when a different decomposition (i.e., a small proofdoor) yields short proofs. As a byproduct, these interpolant lower bounds imply new lower bounds for the partially ordered resolution proof system.

version 2.1