Simple Algorithm
Artificial Intelligence · Deep Layer · 30 min

SAT Solving: DPLL & CDCL

The engines behind modern verification and planning.

In 1971 SAT became the first problem proved NP-complete, the textbook example of intractability. Today SAT solvers routinely settle industrial formulas with millions of variables, verify processor designs and have resolved open problems in mathematics. Both facts are true. The machinery that reconciles them, unit propagation, clause learning and resolution proofs, is this lesson's subject.

What you’ll learn

  • State the Cook–Levin theorem with a proof sketch, and explain why 2-SAT and Horn-SAT are easy.
  • Run DPLL and prove that its UNSAT search trees are tree-like resolution refutations.
  • Trace CDCL conflict analysis (implication graph, 1-UIP, backjumping) and show that learned clauses are resolvents.
  • Use proof complexity to bound what any CDCL solver can do, e.g. on pigeonhole formulas.
  • Describe the random 3-SAT phase transition, separating the empirical threshold near 4.27 from what is proved.

SAT, NP-completeness and the easy cases

DerivationProof sketch
  1. xt,j,s ≡ cell j of row t holds symbol s,O(p(n)2) variablesx_{t,j,s}\ \equiv\ \text{cell } j \text{ of row } t \text{ holds symbol } s,\qquad \order{p(n)^2}\ \text{variables}

    SAT is in NP: a satisfying assignment is a certificate checkable in linear time. For hardness, let a nondeterministic Turing machine MM decide LL in time p(n)p(n). On input ww its computation fits in a p(n)×p(n)p(n)\times p(n) tableau whose row tt is the configuration at time tt. Take one variable per cell and symbol:

  2. φw=φcell∧φstart∧φaccept∧φmove,∣φw∣=O(p(n)2)\varphi_w=\varphi_{\text{cell}}\land\varphi_{\text{start}}\land\varphi_{\text{accept}}\land\varphi_{\text{move}},\qquad |\varphi_w|=\order{p(n)^2}

    Clauses say that each cell holds exactly one symbol, row 0 is the start configuration on ww, some row contains the accepting state, and every 2×32\times3 window of cells is consistent with MM's transition relation. Each window involves a constant number of variables, hence a constant-size CNF:

  3. (ℓ1∨ℓ2∨ℓ3∨ℓ4) ⇝ (ℓ1∨ℓ2∨y)∧(¬y∨ℓ3∨ℓ4)(\ell_1\lor\ell_2\lor\ell_3\lor\ell_4)\ \leadsto\ (\ell_1\lor\ell_2\lor y)\land(\neg y\lor\ell_3\lor\ell_4)

    Satisfying assignments of φw\varphi_w are exactly the accepting computations of MM on ww, so w∈L  ⟺  φww\in L\iff\varphi_w is satisfiable, and φw\varphi_w is built in polynomial time. For 3-SAT, split long clauses with fresh variables, preserving satisfiability:

Some restrictions are easy. 2-SAT takes linear time: each clause a∨ba\lor b is two implications, ¬a⇒b\neg a\Rightarrow b and ¬b⇒a\neg b\Rightarrow a, and the formula is unsatisfiable iff some xx and ¬x\neg x lie in the same strongly connected component of the implication graph (Aspvall, Plass & Tarjan, 1979). Horn-SAT takes linear time by unit propagation (Dowling & Gallier, 1984), and XOR-SAT falls to Gaussian elimination.

Check your understanding

In the implication graph of a 2-CNF formula there is a path from xx to ¬x\neg x, but none from ¬x\neg x to xx. What follows?

  1. The formula is unsatisfiable
  2. Every satisfying assignment, if there is one, sets xx to false
  3. Every satisfying assignment sets xx to true
  4. Nothing: implication paths say nothing about satisfiability
Show the answer

B. Every satisfying assignment, if there is one, sets xx to false

If xx were true, following the implications would force ¬x\neg x, a contradiction; so xx must be false. Unsatisfiability needs paths in both directions, which put xx and ¬x\neg x in one strongly connected component.

DPLL and tree-like resolution

text
function DPLL(F, α) returns a satisfying assignment or UNSAT
  α ← UNIT-PROPAGATE(F, α)        // while a clause has every literal false but one
                                   // unassigned literal, make that literal true
  if some clause of F is false under α then return UNSAT
  if every clause of F is true under α then return α
  x ← an unassigned variable        // branching heuristic
  for each b in {true, false} do   // phase heuristic picks the order
    result ← DPLL(F, α ∪ {x = b})
    if result ≠ UNSAT then return result
  return UNSAT

DPLL (Davis, Logemann & Loveland, 1962) is backtracking on a Boolean CSP whose propagation is unit propagation, which enforces generalized arc consistency on each clause separately. It replaced the resolution-based variable elimination of Davis & Putnam (1960), which ran out of memory.

DerivationProof of the first half
  1. leaf α:Cα∈F,Cα false under α\text{leaf }\alpha:\quad C_\alpha\in F,\quad C_\alpha\ \text{false under}\ \alpha

    Label every failed leaf with a clause of FF that its partial assignment falsifies; one exists, because the leaf failed:

  2. Cα=Resx(C0,C1)=(C0∖{x})∪(C1∖{¬x})false under αC_\alpha=\mathrm{Res}_x(C_0,C_1)=(C_0\setminus\{x\})\cup(C_1\setminus\{\neg x\})\quad\text{false under}\ \alpha

    At a node α\alpha branching on xx, the children carry C1C_1, false under α∪{x=1}\alpha\cup\{x=1\}, and C0C_0, false under α∪{x=0}\alpha\cup\{x=0\}. If C1C_1 does not contain ¬x\neg x, it mentions no literal of xx and is already false under α\alpha: pass it up (likewise C0C_0 without xx). Otherwise resolve on xx:

  3. Croot=□C_{\text{root}}=\square

    Every label stays false under its node's partial assignment. At the root that assignment is empty, and the only clause false under the empty assignment is the empty clause, so the labels form a tree-like refutation. ∎

CDCL: learning from conflicts

Conflict-driven clause learning (GRASP, Marques-Silva & Sakallah, 1996; refined in Chaff, 2001, and MiniSat, 2003) keeps DPLL's skeleton and adds memory. Each assignment records its decision level, the number of decisions above it, and its reason, the clause that forced it; together they form the implication graph. When a clause becomes false, the solver analyzes why. Below, C⊗xDC\otimes_x D is the resolvent of CC and DD on xx.

DerivationConflict analysis on an example
  1. a⏟decision→ c1 b,a→ c2 c,b∧c→ c3 d,c4 false\underbrace{a}_{\text{decision}}\xrightarrow{\ c_1\ }b,\qquad a\xrightarrow{\ c_2\ }c,\qquad b\land c\xrightarrow{\ c_3\ }d,\qquad c_4\ \text{false}

    Take c1=¬a∨bc_1=\neg a\lor b, c2=¬a∨cc_2=\neg a\lor c, c3=¬b∨¬c∨dc_3=\neg b\lor\neg c\lor d, c4=¬b∨¬c∨¬dc_4=\neg b\lor\neg c\lor\neg d, c5=a∨ec_5=a\lor e, c6=a∨¬ec_6=a\lor\neg e. Decide a=1a=1 at level 1. Unit propagation forces bb, cc and dd, and then c4c_4 is false: a conflict.

  2. c4⊗dc3=¬b∨¬c,(¬b∨¬c)⊗cc2=¬a∨¬b,(¬a∨¬b)⊗bc1=¬ac_4\otimes_d c_3=\neg b\lor\neg c,\qquad(\neg b\lor\neg c)\otimes_c c_2=\neg a\lor\neg b,\qquad(\neg a\lor\neg b)\otimes_b c_1=\neg a

    Resolve backward along the trail, starting from the conflict clause, each time on the most recently implied literal:

  3. learn  ¬a\text{learn}\ \ \neg a

    Stop as soon as exactly one literal of the current level remains: the first unique implication point (1-UIP), a node on every path from the decision to the conflict. Here it is the decision itself, and the learned clause is the unit ¬a\neg a.

  4. ¬a,c5⊗ec6=a,a⊗a¬a=□\neg a,\qquad c_5\otimes_e c_6=a,\qquad a\otimes_a\neg a=\square

    Backjump to the second-highest level in the learned clause, here level 0, where it propagates a=0a=0; then c5c_5 forces ee and c6c_6 is false. A conflict at level 0 means UNSAT, and the run has produced a resolution refutation:

Engineering matters as much as theory. Two watched literals per clause mean propagation visits a clause only when a watched literal becomes false. VSIDS branches on variables that appeared in recent conflicts. Frequent restarts escape heavy-tailed runs while keeping the learned clauses. Clause deletion, guided by the literal block distance (Audemard & Simon, 2009), keeps the database small. For UNSAT answers, solvers emit DRAT proofs that independent, even formally verified, checkers validate.

Random 3-SAT and the phase transition

Draw mm clauses uniformly at random, each on 3 distinct variables out of nn with random signs, and let α=m/n\alpha=m/n. With few clauses the formula is almost surely satisfiable; with many, almost surely not. Experiments (Mitchell, Selman & Levesque, 1992; Crawford & Auton, 1996) show the crossover sharpening with nn, and DPLL running times peak right at it: easy, hard, easy.

Predict before you look

For large nn, at what clause-to-variable ratio α\alpha is a random 3-CNF formula satisfiable about half the time?

Show the answer

4.27

Experiments and the statistical-physics prediction put the threshold near α≈4.27\alpha\approx4.27 (the cavity method gives 4.26674.2667). Below it random formulas are almost all satisfiable, above it almost all unsatisfiable. What is proved is weaker, as the next blocks show.

DerivationA first-moment upper bound
  1. Pr⁡[σ⊨F]=(78)m⟹E[X]=2n(78)αn=(2(78)α)n\Pr[\sigma\models F]=\big(\tfrac78\big)^{m}\qquad\Longrightarrow\qquad\E[X]=2^n\big(\tfrac78\big)^{\alpha n}=\Big(2\big(\tfrac78\big)^{\alpha}\Big)^{n}

    Let XX count the satisfying assignments. A fixed assignment falsifies a random 3-clause only if all three literals are false, with probability 1/81/8, and the clauses are independent:

  2. 2(78)α<1  ⟺  α>ln⁡2ln⁡(8/7)≈5.192\big(\tfrac78\big)^{\alpha}<1\iff\alpha>\frac{\ln2}{\ln(8/7)}\approx5.19

    By Markov's inequality, Pr⁡[F satisfiable]=Pr⁡[X≥1]≤E[X]\Pr[F\ \text{satisfiable}]=\Pr[X\ge1]\le\E[X], which tends to 0 once the base drops below 1:

  3. α<3.52: satisfiable w.h.p.,α>4.4898: unsatisfiable w.h.p.\alpha<3.52:\ \text{satisfiable w.h.p.},\qquad\alpha>4.4898:\ \text{unsatisfiable w.h.p.}

    The gap to 4.27 is variance: E[X]\E[X] is dominated by rare formulas with exponentially many clustered solutions. Counting only suitably maximal solutions, and other refinements, sharpen the bounds to:

Key takeaways

  • SAT is NP-complete (Cook–Levin), while 2-SAT, Horn-SAT and XOR-SAT are polynomial; Tseitin's encoding makes 3-CNF a universal input format.
  • DPLL is backtracking with unit propagation, and its UNSAT search trees are tree-like resolution refutations.
  • CDCL learns a clause at each conflict by resolving back to the first UIP, then backjumps. Learned clauses are resolvents, and with restarts CDCL polynomially simulates general resolution.
  • So resolution lower bounds, such as Haken's for pigeonhole formulas, bound every CDCL solver, whatever its heuristics.
  • Random 3-SAT has a sharp transition near α≈4.27\alpha\approx4.27 (empirical); for k=3k=3 proofs give only 3.523.52 to 4.48984.4898, and the exact threshold is known only for large kk.

Check yourself

In the interactive lesson these are scored with your confidence, and what you miss comes back for review.

Question 1

Which statement about the random 3-SAT threshold near α≈4.27\alpha\approx4.27 is correct?

  1. It is an empirical and statistical-physics value; rigorous bounds place the transition between 3.52 and 4.4898, and even the existence of a threshold constant for k=3k=3 is unproved
  2. Friedgut proved that the threshold is exactly 4.27
  3. It is the first-moment bound
  4. Ding, Sly and Sun proved it for every k≥3k\ge3
Show the answer

A. It is an empirical and statistical-physics value; rigorous bounds place the transition between 3.52 and 4.4898, and even the existence of a threshold constant for k=3k=3 is unproved

Friedgut showed the transition is sharp, but at a location that might depend on nn; Ding, Sly and Sun proved the exact threshold only for large kk.

Question 2

Why can adding a learned clause never remove a satisfying assignment?

  1. It is kept only until the next restart
  2. It contains only decision variables
  3. It is derived by resolution from the formula's clauses, so the formula entails it
  4. The solver checks it against every model before adding it
Show the answer

C. It is derived by resolution from the formula's clauses, so the formula entails it

Conflict analysis is a chain of resolution steps, and resolution is sound: every model of the formula satisfies every resolvent.

Question 3

Haken (1985) proved that resolution refutations of the pigeonhole formulas PHPnn+1\mathrm{PHP}^{n+1}_n need size 2Ω(n)2^{\Omega(n)}. What does this imply for CDCL?

  1. Only DPLL without learning is affected
  2. Good heuristics let CDCL avoid the bound
  3. It implies P ≠ NP
  4. Any CDCL run that proves these formulas unsatisfiable takes exponential time, because the run yields a resolution refutation
Show the answer

D. Any CDCL run that proves these formulas unsatisfiable takes exponential time, because the run yields a resolution refutation

A CDCL run's learned clauses and final conflict form a resolution refutation of size polynomial in the run's length, so the run must be exponentially long. Stronger proof systems, such as cutting planes or extended resolution, have polynomial-size pigeonhole proofs.

Question 4

DPLL without learning reports UNSAT after a search tree of ss nodes. What can you conclude about the formula?

  1. It has a tree-like resolution refutation of size O(s)\order{s}
  2. It has no resolution refutation shorter than ss
  3. It has at most ss clauses
  4. It is a 2-CNF formula
Show the answer

A. It has a tree-like resolution refutation of size O(s)\order{s}

Label each failed leaf with a falsified clause and resolve on the branching variable at each internal node: the labels form a tree-like refutation.

Further reading

  • S. A. Cook, "The complexity of theorem-proving procedures," Proceedings of the 3rd ACM Symposium on Theory of Computing (1971), 151–158.
  • M. Davis, G. Logemann & D. Loveland, "A machine program for theorem-proving," Communications of the ACM 5(7) (1962), 394–397.
  • J. P. Marques-Silva & K. A. Sakallah, "GRASP: A search algorithm for propositional satisfiability," IEEE Transactions on Computers 48(5) (1999), 506–521.
  • K. Pipatsrisawat & A. Darwiche, "On the power of clause-learning SAT solvers as resolution engines," Artificial Intelligence 175(2) (2011), 512–525.
  • A. Biere, M. Heule, H. van Maaren & T. Walsh (eds.), Handbook of Satisfiability, 2nd ed. (IOS Press, 2021).