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
SAT is in NP: a satisfying assignment is a certificate checkable in linear time. For hardness, let a nondeterministic Turing machine decide in time . On input its computation fits in a tableau whose row is the configuration at time . Take one variable per cell and symbol:
Clauses say that each cell holds exactly one symbol, row 0 is the start configuration on , some row contains the accepting state, and every window of cells is consistent with 's transition relation. Each window involves a constant number of variables, hence a constant-size CNF:
Satisfying assignments of are exactly the accepting computations of on , so is satisfiable, and 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 is two implications, and , and the formula is unsatisfiable iff some and 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.
In the implication graph of a 2-CNF formula there is a path from to , but none from to . What follows?
- The formula is unsatisfiable
- Every satisfying assignment, if there is one, sets to false
- Every satisfying assignment sets to true
- Nothing: implication paths say nothing about satisfiability
Show the answer
B. Every satisfying assignment, if there is one, sets to false
If were true, following the implications would force , a contradiction; so must be false. Unsatisfiability needs paths in both directions, which put and in one strongly connected component.
DPLL and tree-like resolution
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 UNSATDPLL (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.
Label every failed leaf with a clause of that its partial assignment falsifies; one exists, because the leaf failed:
At a node branching on , the children carry , false under , and , false under . If does not contain , it mentions no literal of and is already false under : pass it up (likewise without ). Otherwise resolve on :
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, is the resolvent of and on .
Take , , , , , . Decide at level 1. Unit propagation forces , and , and then is false: a conflict.
Resolve backward along the trail, starting from the conflict clause, each time on the most recently implied literal:
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 .
Backjump to the second-highest level in the learned clause, here level 0, where it propagates ; then forces and 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 clauses uniformly at random, each on 3 distinct variables out of with random signs, and let . 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 , and DPLL running times peak right at it: easy, hard, easy.
For large , at what clause-to-variable ratio 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 (the cavity method gives ). Below it random formulas are almost all satisfiable, above it almost all unsatisfiable. What is proved is weaker, as the next blocks show.
Let count the satisfying assignments. A fixed assignment falsifies a random 3-clause only if all three literals are false, with probability , and the clauses are independent:
By Markov's inequality, , which tends to 0 once the base drops below 1:
The gap to 4.27 is variance: 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 (empirical); for proofs give only to , and the exact threshold is known only for large .
Check yourself
In the interactive lesson these are scored with your confidence, and what you miss comes back for review.
Which statement about the random 3-SAT threshold near is correct?
- 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 is unproved
- Friedgut proved that the threshold is exactly 4.27
- It is the first-moment bound
- Ding, Sly and Sun proved it for every
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 is unproved
Friedgut showed the transition is sharp, but at a location that might depend on ; Ding, Sly and Sun proved the exact threshold only for large .
Why can adding a learned clause never remove a satisfying assignment?
- It is kept only until the next restart
- It contains only decision variables
- It is derived by resolution from the formula's clauses, so the formula entails it
- 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.
Haken (1985) proved that resolution refutations of the pigeonhole formulas need size . What does this imply for CDCL?
- Only DPLL without learning is affected
- Good heuristics let CDCL avoid the bound
- It implies P ≠ NP
- 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.
DPLL without learning reports UNSAT after a search tree of nodes. What can you conclude about the formula?
- It has a tree-like resolution refutation of size
- It has no resolution refutation shorter than
- It has at most clauses
- It is a 2-CNF formula
Show the answer
A. It has a tree-like resolution refutation of size
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).