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;