Simple Algorithm
Artificial Intelligence · Deep Layer · 28 min

Resolution & Completeness

One inference rule to prove them all.

Resolution has one rule and no axioms, yet it refutes every unsatisfiable set of clauses. It also has a price: some short, obviously true statements, such as "n+1n+1 pigeons do not fit into nn holes", have only exponentially long resolution refutations. This lesson proves the first fact and maps out the second.

What you’ll learn

  • Define clauses, resolvents and refutations precisely, and prove resolution sound.
  • Prove refutation completeness by induction on the number of variables, and read the proof as an algorithm.
  • Distinguish refutation completeness from deductive completeness, and apply complete restrictions and redundancy elimination correctly.
  • State the landmark lower bounds of Tseitin, Haken and Ben-Sasson–Wigderson, and the Cook–Reckhow link to NP versus coNP.

Clauses, resolvents, refutations

Two details matter. Treating clauses as sets silently merges duplicate literals, an operation called factoring that must be made explicit in first-order logic. And resolution cancels one complementary pair per step. From p∨qp\lor q and ¬p∨¬q\neg p\lor\neg q it is tempting to cancel both pairs and conclude □\square, but the two clauses have a common model (pp true, qq false).

Check your understanding

What can resolution correctly derive from the clauses p∨qp\lor q and ¬p∨¬q\neg p\lor\neg q?

  1. The empty clause, so the pair is unsatisfiable
  2. Only the tautologies q∨¬qq\lor\neg q and p∨¬pp\lor\neg p, which are useless
  3. The clause p∨¬qp\lor\neg q
  4. Nothing, because the clauses share no variable
Show the answer

B. Only the tautologies q∨¬qq\lor\neg q and p∨¬pp\lor\neg p, which are useless

Resolving on pp leaves q∨¬qq\lor\neg q; resolving on qq leaves p∨¬pp\lor\neg p. Cancelling both pairs at once would be unsound, since pp true and qq false satisfies both clauses.

Completeness: one rule suffices

DerivationProof of "only if", by induction on the number of variables
  1. S∣p={ C∖{¬p} : C∈S, p∉C },S∣¬p={ C∖{p} : C∈S, ¬p∉C }S|_p=\big\{\,C\setminus\{\neg p\}\ :\ C\in S,\ p\notin C\,\big\},\qquad S|_{\neg p}=\big\{\,C\setminus\{p\}\ :\ C\in S,\ \neg p\notin C\,\big\}

    Write S∣pS|_p for the effect of setting pp true: delete the clauses containing pp and remove ¬p\neg p from the others. Define S∣¬pS|_{\neg p} symmetrically:

  2. S unsatisfiable ⟹ S∣p, S∣¬p unsatisfiable, with one variable fewerS\ \text{unsatisfiable}\ \Longrightarrow\ S|_p,\ S|_{\neg p}\ \text{unsatisfiable, with one variable fewer}

    If SS is unsatisfiable, so are both restrictions: a model of S∣pS|_p on the remaining variables, extended by p=truep=\text{true}, would satisfy every clause of SS. Base case: with no variables left, the only possible clause is □\square, so an unsatisfiable SS contains it.

  3. S⊢Res□  or  {¬p},S⊢Res□  or  {p}S\vdash_{\mathrm{Res}}\square\ \text{ or }\ \{\neg p\},\qquad S\vdash_{\mathrm{Res}}\square\ \text{ or }\ \{p\}

    By induction S∣pS|_p has a refutation. Replay it on the original clauses, restoring ¬p\neg p wherever it was removed: each step is still a legal resolution on a variable other than pp, and the last clause is □\square or {¬p}\{\neg p\}. Likewise S∣¬pS|_{\neg p} yields □\square or {p}\{p\}:

  4. Resp({p},{¬p})=□\mathrm{Res}_p\big(\{p\},\{\neg p\}\big)=\square

    If either replay produced □\square we are done; otherwise one more step resolves {p}\{p\} with {¬p}\{\neg p\}. ∎

So KB⊨α\text{KB}\models\alpha iff saturating CNF(KB∧¬α)\mathrm{CNF}(\text{KB}\land\neg\alpha) produces □\square, and saturation terminates because nn variables allow at most 3n3^n clauses. The proof is itself an algorithm. Eliminating pp by adding all resolvents on pp and deleting the clauses that mention pp is the Davis–Putnam procedure (1960); it preserves satisfiability but can square the number of clauses at each step. DPLL (1962) replaced elimination by splitting on pp, the search reading of the same induction, while bounded variable elimination survives as a preprocessing step in modern SAT solvers.

Restrictions and redundancy

Full saturation generates a flood of useless clauses. Practical provers restrict which pairs may be resolved and delete redundant clauses; the art is doing so without losing completeness.

StrategyRuleRefutation-complete?
Set of support (Wos, Robinson & Carson, 1965)every step uses a clause of the set of support (initially the clauses of ¬α\neg\alpha) or a descendant of oneyes, if the clauses outside the set of support are satisfiable, e.g. a consistent KB
Lineareach step resolves the latest resolvent with an input clause or an earlier resolventyes (Loveland, 1970; Luckham, 1970)
Orderedresolve only on literals that are maximal in a fixed order of the variablesyes; the basis of modern superposition provers
Unitone parent is a unit clauseonly for Horn clauses
Inputone parent is an input clauseonly for Horn clauses; same power as unit resolution (Chang, 1970)
Subsumption, tautology deletiondrop DD if some C⊆DC\subseteq D is present; drop tautologiesyes: these deletions preserve completeness
Think first Unit resolution cannot even start on {p∨q, p∨¬q, ¬p∨q, ¬p∨¬q}\{p\lor q,\ p\lor\neg q,\ \neg p\lor q,\ \neg p\lor\neg q\}. Is the set satisfiable?

No: each of the four assignments to p,qp,q falsifies exactly one clause. Unit resolution needs a unit clause to begin and there is none, so it is stuck on an unsatisfiable set: it is incomplete outside Horn clauses. Full resolution refutes the set in three steps: p∨qp\lor q with p∨¬qp\lor\neg q gives pp, ¬p∨q\neg p\lor q with ¬p∨¬q\neg p\lor\neg q gives ¬p\neg p, and those two give □\square.

Even with every refinement saturation can be slow, and the reason is not engineering: some unsatisfiable formulas have no short resolution refutation at all.

The price of a proof

Measure a refutation by its size, the number of clauses, and its width, the size of its largest clause. Tree-like refutations may not reuse a derived clause (DPLL produces these); general refutations are directed acyclic graphs.

DerivationThe pigeonhole formulas
  1. ⋁j=1npij  for each i,¬pij∨¬pi′j  for each j and i<i′\bigvee_{j=1}^{n}p_{ij}\ \ \text{for each } i,\qquad \neg p_{ij}\lor\neg p_{i'j}\ \ \text{for each } j \text{ and } i<i'

    Variable pijp_{ij} says that pigeon i∈{1,…,n+1}i\in\{1,\dots,n+1\} sits in hole j∈{1,…,n}j\in\{1,\dots,n\}. Every pigeon gets a hole, and no hole holds two pigeons:

  2. (n+1)+n(n+12) clauses(n+1)+n\binom{n+1}{2}\ \text{clauses}

    The formula PHPnn+1\mathrm{PHP}^{n+1}_n has n(n+1)n(n+1) variables and polynomially many clauses, and it is unsatisfiable by a one-line counting argument:

  3. SRes(PHPnn+1)=2Ω(n)S_{\mathrm{Res}}\big(\mathrm{PHP}^{n+1}_n\big)=2^{\Omega(n)}

    Resolution cannot count. Haken (1985) proved that every resolution refutation of it is exponentially long:

  4. Scutting planes(PHPnn+1), Sext. res.(PHPnn+1)=nO(1)S_{\text{cutting planes}}\big(\mathrm{PHP}^{n+1}_n\big),\ S_{\text{ext. res.}}\big(\mathrm{PHP}^{n+1}_n\big)=n^{\order{1}}

    Stronger proof systems escape: cutting planes, which reason with linear inequalities, and extended resolution, which may name subformulas with new variables, both have polynomial-size proofs of the pigeonhole principle.

Predict before you look

How many clauses does PHPnn+1\mathrm{PHP}^{n+1}_n have for n=10n=10 holes?

Show the answer

561 clauses

11 pigeon clauses, plus one clause per pair of the 11 pigeons for each of the 10 holes, 10(112)=55010\binom{11}{2}=550: 561 clauses over 110 variables. Small, yet the shortest resolution refutations of the family grow exponentially in nn.

Cook and Reckhow (1979) explained why this matters. A propositional proof system is a polynomial-time checker whose accepted proofs are exactly the proofs of tautologies, and NP = coNP if and only if some proof system has polynomial-size proofs of every tautology. Superpolynomial lower bounds for ever stronger systems are therefore steps toward NP ≠ coNP, and hence toward P ≠ NP.

Key takeaways

  • Resolution on clauses (sets of literals) is sound: everything derived is entailed. Resolving on two complementary pairs at once is not allowed.
  • Refutation completeness: SS is unsatisfiable iff □∈Res∗(S)\square\in\mathrm{Res}^*(S), proved by induction via the restrictions S∣pS|_p and S∣¬pS|_{\neg p}, the idea behind Davis–Putnam elimination and DPLL splitting.
  • Resolution refutes rather than derives: p∨qp\lor q follows from {p}\{p\} only by refuting its negation.
  • Set of support (with a consistent KB), linear and ordered resolution stay complete; unit and input resolution are complete only for Horn clauses; subsumption and tautology deletion are safe.
  • Lower bounds (Tseitin, Haken, Chvátal–Szemerédi, Ben-Sasson–Wigderson) limit every resolution-based prover, and Cook–Reckhow ties proof length to NP versus coNP.

Check yourself

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

Question 1

Which of these is a theorem about propositional resolution?

  1. If S⊨CS\models C, then CC is derivable from SS by resolution
  2. Every unsatisfiable clause set has a refutation of polynomial size
  3. If SS is unsatisfiable, then □\square is derivable from SS
  4. Unit resolution refutes every unsatisfiable clause set
Show the answer

C. If SS is unsatisfiable, then □\square is derivable from SS

That is refutation completeness. Resolution is not deductively complete, short refutations need not exist, and unit resolution is complete only for Horn clauses.

Question 2

In the completeness proof, why is S∣pS|_p unsatisfiable whenever SS is?

  1. Because S∣pS|_p contains more clauses than SS
  2. Because a model of S∣pS|_p, extended by p=truep=\text{true}, would satisfy every clause of SS
  3. Because resolution is sound
  4. Because S∣pS|_p always contains the empty clause
Show the answer

B. Because a model of S∣pS|_p, extended by p=truep=\text{true}, would satisfy every clause of SS

Clauses containing pp are satisfied by p=truep=\text{true}, and every other clause of SS is a clause of S∣pS|_p, possibly plus the false literal ¬p\neg p.

Question 3

What would follow if some propositional proof system had polynomial-size proofs of all tautologies?

  1. P = NP
  2. Resolution would become complete
  3. NP = coNP
  4. The pigeonhole formulas would be satisfiable
Show the answer

C. NP = coNP

Cook and Reckhow (1979): NP = coNP iff a polynomially bounded proof system exists. A short proof of each tautology would be a certificate for a coNP-complete problem, checkable in polynomial time.

Question 4

Set-of-support resolution, with the clauses of ¬α\neg\alpha as the set of support, is complete for proving KB⊨α\text{KB}\models\alpha when…

  1. always, without conditions
  2. the KB itself is satisfiable
  3. the KB consists of Horn clauses
  4. α\alpha is a single literal
Show the answer

B. the KB itself is satisfiable

Completeness of set of support requires the clauses outside it to be satisfiable. If the KB were inconsistent, the only refutations might use KB clauses alone, which the strategy never resolves with each other.

Further reading

  • J. A. Robinson, "A machine-oriented logic based on the resolution principle," Journal of the ACM 12(1) (1965), 23–41.
  • M. Davis & H. Putnam, "A computing procedure for quantification theory," Journal of the ACM 7(3) (1960), 201–215.
  • A. Haken, "The intractability of resolution," Theoretical Computer Science 39 (1985), 297–308.
  • E. Ben-Sasson & A. Wigderson, "Short proofs are narrow: resolution made simple," Journal of the ACM 48(2) (2001), 149–169.
  • S. A. Cook & R. A. Reckhow, "The relative efficiency of propositional proof systems," Journal of Symbolic Logic 44(1) (1979), 36–50.