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 " pigeons do not fit into 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 and it is tempting to cancel both pairs and conclude , but the two clauses have a common model ( true, false).
What can resolution correctly derive from the clauses and ?
- The empty clause, so the pair is unsatisfiable
- Only the tautologies and , which are useless
- The clause
- Nothing, because the clauses share no variable
Show the answer
B. Only the tautologies and , which are useless
Resolving on leaves ; resolving on leaves . Cancelling both pairs at once would be unsound, since true and false satisfies both clauses.
Completeness: one rule suffices
Write for the effect of setting true: delete the clauses containing and remove from the others. Define symmetrically:
If is unsatisfiable, so are both restrictions: a model of on the remaining variables, extended by , would satisfy every clause of . Base case: with no variables left, the only possible clause is , so an unsatisfiable contains it.
By induction has a refutation. Replay it on the original clauses, restoring wherever it was removed: each step is still a legal resolution on a variable other than , and the last clause is or . Likewise yields or :
If either replay produced we are done; otherwise one more step resolves with . ∎
So iff saturating produces , and saturation terminates because variables allow at most clauses. The proof is itself an algorithm. Eliminating by adding all resolvents on and deleting the clauses that mention 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 , 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.
| Strategy | Rule | Refutation-complete? |
|---|---|---|
| Set of support (Wos, Robinson & Carson, 1965) | every step uses a clause of the set of support (initially the clauses of ) or a descendant of one | yes, if the clauses outside the set of support are satisfiable, e.g. a consistent KB |
| Linear | each step resolves the latest resolvent with an input clause or an earlier resolvent | yes (Loveland, 1970; Luckham, 1970) |
| Ordered | resolve only on literals that are maximal in a fixed order of the variables | yes; the basis of modern superposition provers |
| Unit | one parent is a unit clause | only for Horn clauses |
| Input | one parent is an input clause | only for Horn clauses; same power as unit resolution (Chang, 1970) |
| Subsumption, tautology deletion | drop if some is present; drop tautologies | yes: these deletions preserve completeness |
Think first Unit resolution cannot even start on . Is the set satisfiable?
No: each of the four assignments to 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: with gives , with gives , and those two give .
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.
Variable says that pigeon sits in hole . Every pigeon gets a hole, and no hole holds two pigeons:
The formula has variables and polynomially many clauses, and it is unsatisfiable by a one-line counting argument:
Resolution cannot count. Haken (1985) proved that every resolution refutation of it is exponentially long:
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.
How many clauses does have for holes?
Show the answer
561 clauses
11 pigeon clauses, plus one clause per pair of the 11 pigeons for each of the 10 holes, : 561 clauses over 110 variables. Small, yet the shortest resolution refutations of the family grow exponentially in .
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: is unsatisfiable iff , proved by induction via the restrictions and , the idea behind Davis–Putnam elimination and DPLL splitting.
- Resolution refutes rather than derives: follows from 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.
Which of these is a theorem about propositional resolution?
- If , then is derivable from by resolution
- Every unsatisfiable clause set has a refutation of polynomial size
- If is unsatisfiable, then is derivable from
- Unit resolution refutes every unsatisfiable clause set
Show the answer
C. If is unsatisfiable, then is derivable from
That is refutation completeness. Resolution is not deductively complete, short refutations need not exist, and unit resolution is complete only for Horn clauses.
In the completeness proof, why is unsatisfiable whenever is?
- Because contains more clauses than
- Because a model of , extended by , would satisfy every clause of
- Because resolution is sound
- Because always contains the empty clause
Show the answer
B. Because a model of , extended by , would satisfy every clause of
Clauses containing are satisfied by , and every other clause of is a clause of , possibly plus the false literal .
What would follow if some propositional proof system had polynomial-size proofs of all tautologies?
- P = NP
- Resolution would become complete
- NP = coNP
- 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.
Set-of-support resolution, with the clauses of as the set of support, is complete for proving when…
- always, without conditions
- the KB itself is satisfiable
- the KB consists of Horn clauses
- 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.