An Exponential Separation between Deterministic CDCL and DPLL Solvers

Sahil Samar, Marc Vinyals, Vijay Ganesh · 2026

Read An Exponential Separation between Deterministic CDCL and DPLL Solvers by Sahil Samar, Marc Vinyals, Vijay Ganesh (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2603-16156.txt.

Introduction

Samar, Vinyals, and Ganesh prove an exponential gap between CDCL and DPLL solvers. CDCL learns clauses from conflicts as it searches. DPLL kin stick to tree-like resolution proof shapes. Ordering Principle formulas carry an exponential tree-like lower bound. A set CDCL build with a VSIDS variant solves them fast. Polynomial time in variable count is the proven bound. Any DPLL setup, bound to tree-like proofs, pays exponentially more. The split is exact, not a matter of tuning luck.

Catalog record

CREATORSahil Samar, Marc Vinyals, Vijay Ganesh
YEAR2026
COLLECTIONPAPERS
FORMATTXT
FILE SIZE46259
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2603.16156

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

An Exponential Separation between Deterministic CDCL and DPLL Solvers Sahil Samar, Marc Vinyals, Vijay Ganesh Abstract We prove that there exists a deterministic configuration of Conflict Driven Clause Learning (CDCL) SAT solvers using a variant of the VSIDS branching heuristic that solves instances of the Ordering Principle (OP) CNF formulas in time polynomial in n n , where n n is the number of variables in such formulas. Since tree-like resolution is known to have an exponential lower bound for proof size for OP formulas, it follows that CDCL under this configuration has an exponential separation with any solver that is polynomially equivalent to tree-like resolution and therefore any configuration of DPLL SAT solvers. School of Computer Science, Georgia Institute of Technology, [email protected] of Computer Science, University of Auckland, New [email protected] School of Computer Science, Georgia Institute of Technology, [email protected] ccs Theory of computation Logic keywords SAT Solvers, Proof Systems, VSIDS † † runningauthor: S. Samar, M. Vinyals, and V.Ganesh † † copyright: Sahil Samar, Marc Vinyals, and Vijay Ganesh † † editors: John Q. Open and Joan R. Access † † event-title: 42nd Conference on Very Important Topics (CVIT 2016) † † event-shorttitle: CVIT 2016 † † event-acronym: CVIT † † year: 2016 † † event-date: December 24–27, 2016 † † event-location: Little Whinging, United Kingdom † † series-volume: 42 † † articleno: 23 1 Introduction Empirically speaking, it is well-known that practical SAT solvers based on the CDCL algorithm are efficient for certain classes of problems [ 10 ] . It is also well-known that SAT solvers based on CDCL are much more efficient than their DPLL counterparts, and that the main reason for that is clause learning. This is supported both experimentally, as shown in ablation studies [ 11 , 8 ] , as well as theoretically, given how DPLL is constrained by the very weak tree-like resolution proof system, while CDCL escapes that constraint. Not only CDCL is potentially stronger than tree-like resolution, there is an equivalence between algorithms and proof systems. Assuming both algorithms employ optimal heuristics, DPLL becomes equivalent to tree-like resolution, while CDCL becomes equivalent to general resolution [ 15 , 2 ] . Since there exist formulas that have polynomially long resolution proofs but require exponentially long tree-like resolution proofs, as a result of the separation between proof systems we obtain an exponential separation between algorithms. However, there is a caveat to the equivalence and separation results, which is that they only apply to nondeterministic algorithms using optimal heuristics given by an unrealistic oracle. The fact that a short proof exists does not mean that a deterministic algorithm is necessarily able to find it. Whether that is possible is called the automatability problem [ 6 ] , and it is an active area of study. In the case of resolution, a breakthrough result proved that no deterministic algorithm can always find short resolution proofs unless \mathsf{P}=\mathsf{NP} [ 3 ] . To be a bit more precise, there is only one heuristic that is required to be nondeterministic for CDCL to simulate resolution, and that is the branching heuristic, which determines the next variable to be branched upon. A randomized heuristic is enough for CDCL to simulate bounded-width resolution, and if the heuristic is fixed and deterministic then it is known unconditionally—independently of whether \mathsf{P}=\mathsf{NP} —that CDCL cannot always find short resolution proofs when the branching heuristic is VSIDS-like [ 18 ] or ordered [ 14 ] . Therefore, we are still left with the question of explaining the power of CDCL with practical branching heuristics such as VSIDS, and in particular whether there exists an exponential separation between DPLL and CDCL in a practical setting, and with practical heuristics. In other words, whether there are formulas that cannot be solved unless CDCL exploits the full power of resolution. We address this question here. Two families of formulas that exponentially separate tree-like and general resolution, and therefore are candidates to answer our question, are pebbling formulas and the ordering principle. The first family of formulas has been studied in a proof system more closely resembling CDCL [ 9 ] , but still assuming an optimal decision heuristic. The second family is what concerns us. The complexity of resolution proofs of the ordering principle has been widely studied. The formulas were introduced as a tricky family that could be solved using certain symmetry breaking properties but appeared hard for resolution [ 12 ] . They were later shown to have in fact short resolution proofs [ 17 ] but to require exponentially long tree-like resolution proofs [ 5 ] . Furthermore, a modified version of these formulas was used to exponentially separate regular from general resolution [ 1 ] . What makes these formulas tricky is that any resolution proofs require learning clauses containing many variables, which is usually an indicator of hardness. In a well-defined sense, these formulas are just at the boundary of formulas that are easy versus hard for resolution: a formula over n variables that requires clauses containing \Omega(\sqrt{n}) variables to prove, such as the ordering principle, requires exponentially long tree-like resolution proofs, and a formula whose proof requires clauses containing \Omega(n^{1/2+\epsilon}) variables requires exponentially long resolution proofs. This makes the ordering principle a very interesting case study for the capabilities of any resolution-based algorithm. Furthermore, empirical work gives strong evidence that the Glucose SAT Solver with VSIDS decay factor 0.6 can solve OP instances in polynomial time, but not with a larger decay factor of 0.95 [ 8 ] , further adding to the mystery. In this paper, we prove that CDCL with either the VSIDS or VMTF heuristics solves the ordering principle family of formulas in polynomial time. To the best of our knowledge, this is the first result showing a polynomial upper bound for a completely deterministic configuration of CDCL solvers, simultaneously exponentially separating it from all configurations of DPLL SAT solvers. To be more precise, we use VSIDS with decay factor at most 1/2 (which is equivalent to a variant of VMTF), fixed phase value selection, restarts after every conflict, no clause deletion, and 1UIP clause learning. Our proof heavily uses the fact that the decay factor is at most 1/2 , which is perhaps not surprising in view of how an aggressive decay factor has also been experimentally observed to be required to solve instances of the ordering principle. Most assumptions we make about the deterministic configuration of CDCL studied here are inspired by practice or fairly standard in theoretical papers, except perhaps fixed phase value selection. For example, frequent restarts and no deletions are required in the existing proofs that nondeterministic CDCL simulates resolution, while 1UIP is the de-facto standard clause learning heuristic in modern CDCL SAT solvers. An immediate corollary of our result, given that there is an exponential lower bound on the size of tree-like resolution proofs of the ordering principle, and that the DPLL algorithm is captured by tree-like resolution, is that there is an exponential separation between deterministic CDCL and nondeterministic DPLL. 2 Preliminaries In this section, we briefly outline the definitions used in the rest of this paper. 2.1 Ordering Principle \displaystyle A_{n} \displaystyle=\bigwedge_{\begin{subarray}{c}1\leq i,j,k\leq n\\ i\neq j,k\neq i,j\neq

Read the complete text