Skip to main content

logicaffeine_proof/
inprocess.rs

1//! Certified inprocessing: clause-database simplifications that emit a machine-checkable proof.
2//!
3//! Where a normal SAT solver simplifies for speed, here every simplification carries its own
4//! certificate — bounded variable elimination adds RUP resolvents and deletes the eliminated
5//! variable's clauses; vivification replaces a clause with a RUP-shorter one. Composed with the
6//! refutation, the whole run stays independently checkable by [`crate::pr::check_pr_refutation`].
7//! This is the certified analogue of the inprocessing that makes Kissat/CaDiCaL fast — a real
8//! differentiator: nobody ships *certified* inprocessing.
9
10use crate::cdcl::{Lit, Var};
11use crate::proof::ProofStep;
12
13/// Resolve `a` (which contains `+x`) with `b` (which contains `¬x`) on `x`: the union of the two
14/// clauses minus both `x` literals. `None` if the resolvent is a tautology (contains some literal
15/// and its negation), which contributes nothing.
16fn resolve(a: &[Lit], b: &[Lit], x: Var) -> Option<Vec<Lit>> {
17    let mut r: Vec<Lit> = a.iter().copied().filter(|l| l.var() != x).collect();
18    for &l in b {
19        if l.var() != x && !r.contains(&l) {
20            r.push(l);
21        }
22    }
23    if r.iter().any(|&l| r.contains(&l.negated())) {
24        return None; // tautology
25    }
26    Some(r)
27}
28
29/// Try to eliminate variable `x` from `clauses` by Davis-Putnam resolution. Returns the new clause
30/// set and the proof steps (RUP resolvents, then the deletions of `x`'s clauses) — but only when
31/// `x` actually occurs and elimination does not grow the clause count (the standard BVE bound).
32/// `None` otherwise. Verdict-invariant: a model of the result extends to a model of the input.
33pub fn eliminate_variable(clauses: &[Vec<Lit>], x: Var) -> Option<(Vec<Vec<Lit>>, Vec<ProofStep>)> {
34    let (pos, neg) = (Lit::pos(x), Lit::neg(x));
35    let pos_clauses: Vec<&Vec<Lit>> = clauses.iter().filter(|c| c.contains(&pos)).collect();
36    let neg_clauses: Vec<&Vec<Lit>> = clauses.iter().filter(|c| c.contains(&neg)).collect();
37    if pos_clauses.is_empty() && neg_clauses.is_empty() {
38        return None; // `x` does not occur
39    }
40    // All non-tautological resolvents.
41    let mut resolvents: Vec<Vec<Lit>> = Vec::new();
42    for a in &pos_clauses {
43        for b in &neg_clauses {
44            if let Some(r) = resolve(a, b, x) {
45                resolvents.push(r);
46            }
47        }
48    }
49    // Bound: never grow the clause database.
50    if resolvents.len() > pos_clauses.len() + neg_clauses.len() {
51        return None;
52    }
53    // Proof: each resolvent is RUP (its two parents force `x` and `¬x` under `¬resolvent`); then
54    // delete every clause mentioning `x`. Resolvents are added BEFORE the deletions so their RUP
55    // check still sees the parents.
56    let mut steps: Vec<ProofStep> = resolvents
57        .iter()
58        .map(|r| ProofStep::Rup(r.clone()))
59        .collect();
60    for c in pos_clauses.iter().chain(neg_clauses.iter()) {
61        steps.push(ProofStep::Delete((*c).clone()));
62    }
63    let mut new_clauses: Vec<Vec<Lit>> = clauses
64        .iter()
65        .filter(|c| !c.contains(&pos) && !c.contains(&neg))
66        .cloned()
67        .collect();
68    new_clauses.extend(resolvents);
69    Some((new_clauses, steps))
70}
71
72/// Bounded variable elimination over the whole formula: repeatedly eliminate every variable whose
73/// elimination is non-growing, until a fixpoint (capped at a few passes). Returns the simplified
74/// clause set and the composed proof steps.
75pub fn bve(num_vars: usize, clauses: &[Vec<Lit>]) -> (Vec<Vec<Lit>>, Vec<ProofStep>) {
76    let mut cur = clauses.to_vec();
77    let mut steps: Vec<ProofStep> = Vec::new();
78    for _pass in 0..4 {
79        let mut changed = false;
80        for x in 0..num_vars as Var {
81            if let Some((next, s)) = eliminate_variable(&cur, x) {
82                cur = next;
83                steps.extend(s);
84                changed = true;
85            }
86        }
87        if !changed {
88            break;
89        }
90    }
91    (cur, steps)
92}
93
94/// Equivalent-literal detection via the binary-implication graph's strongly-connected components. Each
95/// 2-clause `(a ∨ b)` contributes the implications `¬a → b` and `¬b → a`; literals in one SCC are logically
96/// equivalent. If some `x` and `¬x` share an SCC, the binary clauses alone force `x ≡ ¬x` — UNSAT — and we
97/// return the RUP certificate (`(x)`, `(¬x)`, then `⊥`, each RUP-derivable by propagation along the chain).
98/// Otherwise returns the SCC representative for each literal, so equal literals can be substituted (a sound
99/// variable-reduction speedup). Iterative Tarjan; nodes are the `2·num_vars` literals (`2v` = `+v`, `2v+1` = `¬v`).
100fn lit_node(l: Lit) -> usize {
101    (l.var() as usize) * 2 + if l.is_positive() { 0 } else { 1 }
102}
103pub enum EquivResult {
104    /// `x ≡ ¬x` forced by the 2-clauses — UNSAT, with a RUP certificate.
105    Unsat(Vec<ProofStep>),
106    /// Per-literal SCC id; two literals with the same id are equivalent (substitutable).
107    Classes(Vec<usize>),
108}
109pub fn equivalent_literal_scc(num_vars: usize, clauses: &[Vec<Lit>]) -> EquivResult {
110    let n = num_vars * 2;
111    let mut adj: Vec<Vec<usize>> = vec![Vec::new(); n];
112    for c in clauses {
113        if c.len() == 2 {
114            let (a, b) = (c[0], c[1]);
115            adj[lit_node(a.negated())].push(lit_node(b)); // ¬a → b
116            adj[lit_node(b.negated())].push(lit_node(a)); // ¬b → a
117        }
118    }
119    // Iterative Tarjan SCC.
120    let mut index = vec![usize::MAX; n];
121    let mut low = vec![0usize; n];
122    let mut on_stack = vec![false; n];
123    let mut stack: Vec<usize> = Vec::new();
124    let mut comp = vec![usize::MAX; n];
125    let mut next_index = 0usize;
126    let mut next_comp = 0usize;
127    for start in 0..n {
128        if index[start] != usize::MAX {
129            continue;
130        }
131        let mut call: Vec<(usize, usize)> = vec![(start, 0)];
132        while let Some(&(v, pi)) = call.last() {
133            if pi == 0 {
134                index[v] = next_index;
135                low[v] = next_index;
136                next_index += 1;
137                stack.push(v);
138                on_stack[v] = true;
139            }
140            if pi < adj[v].len() {
141                let w = adj[v][pi];
142                call.last_mut().unwrap().1 += 1;
143                if index[w] == usize::MAX {
144                    call.push((w, 0));
145                } else if on_stack[w] {
146                    low[v] = low[v].min(index[w]);
147                }
148            } else {
149                if low[v] == index[v] {
150                    loop {
151                        let w = stack.pop().unwrap();
152                        on_stack[w] = false;
153                        comp[w] = next_comp;
154                        if w == v {
155                            break;
156                        }
157                    }
158                    next_comp += 1;
159                }
160                call.pop();
161                if let Some(&(p, _)) = call.last() {
162                    low[p] = low[p].min(low[v]);
163                }
164            }
165        }
166    }
167    for v in 0..num_vars {
168        if comp[v * 2] == comp[v * 2 + 1] {
169            let (x, nx) = (Lit::pos(v as Var), Lit::neg(v as Var));
170            return EquivResult::Unsat(vec![
171                ProofStep::Rup(vec![nx]),
172                ProofStep::Rup(vec![x]),
173                ProofStep::Rup(vec![]),
174            ]);
175        }
176    }
177    EquivResult::Classes(comp)
178}
179
180/// Full Davis–Putnam bucket elimination in min-degree order, allowing intermediate growth but capping every
181/// resolvent at `width_cap`. If it reaches `⊥`, returns the RUP-resolvents-then-deletions proof — a
182/// width-`≤width_cap` resolution refutation, i.e. a `2^width_cap·n` certificate that crushes every
183/// bounded-treewidth family. Returns `None` the moment a resolvent would exceed the cap (high treewidth — the
184/// certificate would be exponential, which is exactly the Ben-Sasson–Wigderson hardness). Sound: every step is
185/// RUP/Delete and independently re-checkable by [`crate::pr::check_pr_refutation`].
186pub fn bucket_elimination_refute(
187    num_vars: usize,
188    clauses: &[Vec<Lit>],
189    width_cap: usize,
190) -> Option<Vec<ProofStep>> {
191    let mut cur: Vec<Vec<Lit>> = clauses.to_vec();
192    let mut steps: Vec<ProofStep> = Vec::new();
193    for _ in 0..=num_vars {
194        if cur.iter().any(|c| c.is_empty()) {
195            return Some(steps);
196        }
197        let mut vars: Vec<Var> = cur.iter().flatten().map(|l| l.var()).collect();
198        vars.sort_unstable();
199        vars.dedup();
200        if vars.is_empty() {
201            break;
202        }
203        let v = *vars
204            .iter()
205            .min_by_key(|&&v| {
206                cur.iter()
207                    .filter(|c| c.iter().any(|l| l.var() == v))
208                    .count()
209            })
210            .unwrap();
211        let (pos, neg) = (Lit::pos(v), Lit::neg(v));
212        let pos_c: Vec<Vec<Lit>> = cur.iter().filter(|c| c.contains(&pos)).cloned().collect();
213        let neg_c: Vec<Vec<Lit>> = cur.iter().filter(|c| c.contains(&neg)).cloned().collect();
214        // Even under the min-degree order the resolvent product `|pos| · |neg|` can explode once a dense
215        // (high-treewidth) core is reached — each resolvent stays narrow (so the width cap never trips)
216        // yet there are quadratically many. Bail before doing that work: a bounded-treewidth family keeps
217        // this product small, so declining here costs nothing there while a dense family (e.g. Ramsey)
218        // exits in microseconds instead of grinding for seconds. The certificate would be exponential
219        // anyway (the same Ben-Sasson–Wigderson hardness the width cap guards).
220        if pos_c.len().saturating_mul(neg_c.len()) > 16_384 {
221            return None;
222        }
223        let mut resolvents: Vec<Vec<Lit>> = Vec::new();
224        for a in &pos_c {
225            for b in &neg_c {
226                if let Some(r) = resolve(a, b, v) {
227                    if r.len() > width_cap {
228                        return None; // exceeds the width cap — high treewidth, decline
229                    }
230                    resolvents.push(r);
231                }
232            }
233        }
234        for r in &resolvents {
235            steps.push(ProofStep::Rup(r.clone()));
236        }
237        for c in pos_c.iter().chain(neg_c.iter()) {
238            steps.push(ProofStep::Delete(c.clone()));
239        }
240        cur.retain(|c| !c.contains(&pos) && !c.contains(&neg));
241        cur.extend(resolvents);
242        if cur.len() > 50_000 {
243            return None; // database blow-up guard
244        }
245    }
246    if cur.iter().any(|c| c.is_empty()) {
247        Some(steps)
248    } else {
249        None
250    }
251}
252
253/// Vivify a clause: drop every literal whose removal leaves a clause still RUP-implied by `db`.
254/// Returns the strengthened (shorter) clause, or `None` if nothing could be removed. The result
255/// is a sub-clause logically equivalent in context, so it is verdict-invariant.
256pub fn vivify_clause(num_vars: usize, db: &[Vec<Lit>], c: &[Lit]) -> Option<Vec<Lit>> {
257    let mut cur = c.to_vec();
258    let mut improved = false;
259    let mut i = 0;
260    while cur.len() > 1 && i < cur.len() {
261        let mut without = cur.clone();
262        without.remove(i);
263        if crate::rup::is_rup(num_vars, db, &without) {
264            cur = without; // this literal is redundant
265            improved = true;
266        } else {
267            i += 1;
268        }
269    }
270    improved.then_some(cur)
271}
272
273/// Vivify the whole database: replace each clause with its RUP-strengthened form, emitting an
274/// `Rup(shorter)` then `Delete(original)` per improvement. Shorter clauses propagate and delete
275/// better. The composed steps keep the run independently checkable.
276pub fn vivify(num_vars: usize, clauses: &[Vec<Lit>]) -> (Vec<Vec<Lit>>, Vec<ProofStep>) {
277    let mut cur = clauses.to_vec();
278    let mut steps: Vec<ProofStep> = Vec::new();
279    for idx in 0..cur.len() {
280        let c = cur[idx].clone();
281        if c.len() <= 1 {
282            continue;
283        }
284        if let Some(c2) = vivify_clause(num_vars, &cur, &c) {
285            steps.push(ProofStep::Rup(c2.clone()));
286            steps.push(ProofStep::Delete(c.clone()));
287            cur[idx] = c2;
288        }
289    }
290    (cur, steps)
291}
292
293#[cfg(test)]
294#[path = "../../logicaffeine_tests/unit/logicaffeine_proof/inprocess/tests.rs"]
295mod tests;