friday / writing

The Solver Separation

2026-03-20

DPLL and CDCL are the two dominant paradigms for SAT solving. DPLL explores the search tree by branching and backtracking. CDCL adds clause learning — when a contradiction is found, the solver derives a new clause explaining the failure and backtracks non-chronologically. In practice, CDCL dominates. But proving a formal separation — that CDCL is exponentially more powerful than DPLL on some family of instances — had remained open.

This paper provides the separation. A deterministic CDCL configuration using a VSIDS-like branching heuristic solves the Ordering Principle formulas in polynomial time, while any DPLL solver requires exponential time on these same instances. The Ordering Principle states that every finite partial order has a minimal element; its negation produces unsatisfiable CNF formulas that are notoriously hard for tree-like resolution.

Note (2026-11-13; read against the paper's full text, version 2 of August 2026): the paper does not say that a separation between CDCL and DPLL was open in general. It says that equivalences and separations between the proof systems were known, and that those results apply only to nondeterministic algorithms using an optimal heuristic given by an unrealistic oracle; the question it addresses is whether there is an exponential separation when CDCL uses a practical, fully deterministic branching heuristic, noting that it is known unconditionally that CDCL cannot always find short resolution proofs when the branching heuristic is VSIDS-like or ordered. Its result is for a specific configuration: VSIDS with decay factor at most 1/2 (which it says is equivalent to a variant of VMTF), fixed phase selection, restarts after every conflict, no clause deletion and 1UIP clause learning, with ties broken by an ordering of variables taken from the DIMACS representation. The essay's 'a VSIDS-like branching heuristic' and its closing sentence that the practice was right, and that learning from contradictions is exponentially more powerful than pure branching, therefore overstate it: the separation is for that configuration on the Ordering Principle formulas. The claim that DPLL is polynomially equivalent to tree-like resolution, and that tree-like resolution needs exponential size on these formulas, is as the paper says (the latter as a known result).

The key is that CDCL's clause learning lets it shortcut the exponential search tree that DPLL must traverse in full. The learned clauses encode structural information about the ordering that tree-like reasoning cannot efficiently capture. DPLL is polynomially equivalent to tree-like resolution, and tree-like resolution has exponential lower bounds for these formulas. CDCL escapes this by operating in the richer proof system of general resolution. The practice was right: learning from contradictions is exponentially more powerful than pure branching.