Skip to main content

logicaffeine_proof/
sdcl.rs

1//! Satisfaction-Driven Clause Learning (Heule, Kiesl & Seidl) — the engine that reasons at the
2//! Extended-Frege level by *discovering* propagation-redundant clauses, not just learning implied
3//! ones. It is symmetry breaking taken to its limit: where certified symmetry breaking needs an
4//! automorphism to supply a witness, SDCL **finds the witness by solving the positive reduct** — a
5//! smaller SAT problem — so it works on *any* structure, symmetric or not.
6//!
7//! When the search is stuck at a partial assignment `α` it cannot extend, the clause `C = ¬α` would
8//! block that subtree. `C` is propagation-redundant iff the positive reduct `{C} ∪ {D ∈ F : α ⊨ D}`
9//! is satisfiable; a satisfying `ω` is the witness. Every clause this finds is gated through the
10//! independent PR checker ([`crate::pr::is_pr`]), so it is sound by construction and emits a
11//! checkable PR step — the same machine-checkable currency as the rest of the campaign.
12
13use crate::cdcl::{Lit, SolveResult, Solver, Var};
14use crate::pr::{check_pr_refutation, is_pr};
15use crate::proof::{Perm, ProofStep, Witness};
16use crate::sym_certify::CertifiedRefutation;
17use crate::symmetry_detect::find_generators;
18use std::collections::HashSet;
19
20/// From a "stuck" partial assignment `alpha` (its true-literals), try to discover a PR clause
21/// `C = ¬alpha` that blocks it, via the positive reduct. Returns the clause and its witness, both
22/// verified by the PR checker (fail-closed). This is the SDCL primitive — a universal,
23/// automorphism-free generalization of certified symmetry breaking.
24pub fn find_pr_clause(
25    num_vars: usize,
26    clauses: &[Vec<Lit>],
27    alpha: &[Lit],
28) -> Option<(Vec<Lit>, Witness)> {
29    // C = ¬alpha — every literal of alpha, negated.
30    let c: Vec<Lit> = alpha.iter().map(|l| l.negated()).collect();
31    if c.is_empty() {
32        return None;
33    }
34    // Positive reduct: a witness ω must satisfy C and every clause alpha already satisfies. The
35    // witness is read off over just the *relevant* variables (C's plus those satisfied clauses'),
36    // so untouched clauses impose no obligation on the PR check.
37    let mut relevant: HashSet<Var> = c.iter().map(|l| l.var()).collect();
38    let mut reduct: Vec<Vec<Lit>> = vec![c.clone()];
39    for d in clauses {
40        if d.iter().any(|l| alpha.contains(l)) {
41            for l in d {
42                relevant.insert(l.var());
43            }
44            reduct.push(d.clone());
45        }
46    }
47    let mut solver = Solver::new(num_vars);
48    for cl in &reduct {
49        solver.add_clause(cl.clone());
50    }
51    if let SolveResult::Sat(model) = solver.solve() {
52        let omega: Vec<Lit> = relevant
53            .iter()
54            .map(|&v| Lit::new(v, model[v as usize]))
55            .collect();
56        let witness = Witness::Assignment(omega);
57        // Independent sound gate: only return a clause the PR checker actually certifies.
58        if is_pr(num_vars, clauses, &c, &witness) {
59            return Some((c, witness));
60        }
61    }
62    None
63}
64
65/// A fully automatic SDCL refutation: repeatedly discover propagation-redundant **unit** clauses
66/// (by probing each literal as a stuck state and solving the positive reduct), add them as PR
67/// steps, until the formula collapses to a RUP refutation. No symmetry, no problem-specific
68/// knowledge, no hint — the solver finds the Extended-Frege proof itself, and emits it for the
69/// independent checker. This is the universal engine the whole campaign was climbing toward.
70/// The SDCL discovery core: repeatedly probe each literal and add any propagation-redundant clause
71/// the unified finder certifies (positive-reduct assignment witness, or a substitution witness from
72/// the round's freshly-detected symmetry group), until no more are found. Returns the augmented
73/// database (a superset of the input — every added clause is satisfiability-preserving) and the PR
74/// proof steps that justify the additions.
75fn sdcl_discover(num_vars: usize, clauses: &[Vec<Lit>]) -> (Vec<Vec<Lit>>, Vec<ProofStep>) {
76    let mut db = clauses.to_vec();
77    let mut steps: Vec<ProofStep> = Vec::new();
78    let cap = num_vars * num_vars + 8;
79    while steps.len() < cap {
80        let gens = find_generators(num_vars, &db);
81        let mut progressed = false;
82        'probe: for v in 0..num_vars as Var {
83            for &val in &[true, false] {
84                let alpha = [Lit::new(v, val)];
85                if let Some((c, w)) = find_pr_clause_unified(num_vars, &db, &alpha, &gens) {
86                    if !db.iter().any(|d| d == &c) {
87                        db.push(c.clone());
88                        steps.push(ProofStep::Pr {
89                            clause: c,
90                            witness: w,
91                        });
92                        progressed = true;
93                        break 'probe;
94                    }
95                }
96            }
97        }
98        if !progressed {
99            break;
100        }
101    }
102    (db, steps)
103}
104
105pub fn sdcl_refute(num_vars: usize, clauses: &[Vec<Lit>]) -> CertifiedRefutation {
106    let (db, mut steps) = sdcl_discover(num_vars, clauses);
107    let sbp_clauses = steps.len();
108    let mut solver = Solver::new(num_vars);
109    for c in &db {
110        solver.add_clause(c.clone());
111    }
112    match solver.solve() {
113        SolveResult::Sat(_) => CertifiedRefutation {
114            refuted: false,
115            sbp_clauses,
116            steps,
117        },
118        SolveResult::Unsat => {
119            for lc in solver.learned() {
120                steps.push(ProofStep::Rup(lc.lits.clone()));
121            }
122            // Fail-closed: the composed proof, or a plain CDCL refutation if it doesn't certify.
123            if check_pr_refutation(num_vars, clauses, &steps) {
124                CertifiedRefutation {
125                    refuted: true,
126                    sbp_clauses,
127                    steps,
128                }
129            } else {
130                CertifiedRefutation {
131                    refuted: true,
132                    sbp_clauses: 0,
133                    steps: plain_cdcl_refutation(num_vars, clauses),
134                }
135            }
136        }
137    }
138}
139
140/// The verdict of the unified certified solver.
141pub enum CertifiedOutcome {
142    /// Unsatisfiable, with a machine-checkable refutation (PR discovery steps + RUP learned steps)
143    /// that re-checks against the original formula, and how many clauses SDCL discovered.
144    Unsat {
145        steps: Vec<ProofStep>,
146        discovered: usize,
147    },
148    /// Satisfiable, with a model over `0..num_vars`.
149    Sat(Vec<bool>),
150}
151
152/// Propagate only forced root literals, then validate a complete witness
153/// against the original input. This never declares UNSAT and never branches:
154/// inconclusive or conflicting inputs keep the existing certified SDCL path.
155fn checked_root_model(num_vars: usize, clauses: &[Vec<Lit>]) -> Option<Vec<bool>> {
156    if clauses
157        .iter()
158        .flatten()
159        .any(|lit| lit.var() as usize >= num_vars)
160    {
161        return None;
162    }
163    let mut assignment = vec![None; num_vars];
164    loop {
165        let mut changed = false;
166        for clause in clauses {
167            let mut satisfied = false;
168            let mut unassigned = None;
169            let mut multiple = false;
170            for &literal in clause {
171                match assignment[literal.var() as usize] {
172                    Some(value) if value == literal.is_positive() => {
173                        satisfied = true;
174                        break;
175                    }
176                    Some(_) => {}
177                    None => match unassigned {
178                        None => unassigned = Some(literal),
179                        Some(previous) if previous != literal => multiple = true,
180                        Some(_) => {}
181                    },
182                }
183            }
184            if satisfied {
185                continue;
186            }
187            let literal = unassigned?;
188            if !multiple {
189                assignment[literal.var() as usize] = Some(literal.is_positive());
190                changed = true;
191            }
192        }
193        if !changed {
194            break;
195        }
196    }
197    let model: Vec<bool> = assignment
198        .into_iter()
199        .map(|value| value.unwrap_or(false))
200        .collect();
201    // The cheap root path earns SAT only by a witness that checks EVERY input
202    // clause, including clauses that propagation never used.
203    clauses
204        .iter()
205        .all(|clause| {
206            clause
207                .iter()
208                .any(|lit| model[lit.var() as usize] == lit.is_positive())
209        })
210        .then_some(model)
211}
212
213/// The unified certified solver. Root unit propagation first tries to establish
214/// a model, checked against every original clause. Otherwise SDCL discovers
215/// propagation-redundant clauses through positive reducts and live symmetry,
216/// then CDCL solves the augmented formula. UNSAT returns an independently
217/// checked refutation; SAT returns a model of the original input.
218pub fn solve_certified(num_vars: usize, clauses: &[Vec<Lit>]) -> CertifiedOutcome {
219    solve_with_discovery(num_vars, clauses, || sdcl_discover(num_vars, clauses))
220}
221
222fn solve_with_discovery(
223    num_vars: usize,
224    clauses: &[Vec<Lit>],
225    discover: impl FnOnce() -> (Vec<Vec<Lit>>, Vec<ProofStep>),
226) -> CertifiedOutcome {
227    if let Some(model) = checked_root_model(num_vars, clauses) {
228        return CertifiedOutcome::Sat(model);
229    }
230    let (db, mut steps) = discover();
231    let discovered = steps.len();
232    let mut solver = Solver::new(num_vars);
233    for c in &db {
234        solver.add_clause(c.clone());
235    }
236    match solver.solve() {
237        SolveResult::Sat(model) => CertifiedOutcome::Sat(model),
238        SolveResult::Unsat => {
239            for lc in solver.learned() {
240                steps.push(ProofStep::Rup(lc.lits.clone()));
241            }
242            // FAIL-CLOSED: a certified solver must never return an unchecked proof. Verify the
243            // composed refutation; if the SDCL composition does not certify, fall back to a plain
244            // CDCL refutation of the original (always RUP-checkable). The original is UNSAT iff the
245            // augmented database is, since every discovered clause is satisfiability-preserving.
246            if check_pr_refutation(num_vars, clauses, &steps) {
247                CertifiedOutcome::Unsat { steps, discovered }
248            } else {
249                CertifiedOutcome::Unsat {
250                    steps: plain_cdcl_refutation(num_vars, clauses),
251                    discovered: 0,
252                }
253            }
254        }
255    }
256}
257
258/// A plain CDCL refutation of `clauses` as RUP proof steps — always re-checkable. The certified
259/// fallback that guarantees [`solve_certified`] and [`sdcl_refute`] never emit an unchecked proof,
260/// and the universal source of a `cake_lpr`-checkable LRAT certificate for any UNSAT instance.
261pub fn plain_cdcl_refutation(num_vars: usize, clauses: &[Vec<Lit>]) -> Vec<ProofStep> {
262    let mut solver = Solver::new(num_vars);
263    for c in clauses {
264        solver.add_clause(c.clone());
265    }
266    let _ = solver.solve();
267    solver
268        .learned()
269        .iter()
270        .map(|lc| ProofStep::Rup(lc.lits.clone()))
271        .collect()
272}
273
274/// The unified PR-clause finder: the universal SDCL discovery (positive-reduct assignment witness)
275/// PLUS the scalable symmetry path (substitution witnesses from the supplied generators). The
276/// assignment witness is general but can fail to certify at scale (it needs `F|α` UP-refutable); a
277/// substitution witness from a live automorphism certifies the lead clauses at *any* size via an
278/// immediate conflict. Trying both gives SDCL that discovers AND scales.
279pub fn find_pr_clause_unified(
280    num_vars: usize,
281    clauses: &[Vec<Lit>],
282    alpha: &[Lit],
283    generators: &[Perm],
284) -> Option<(Vec<Lit>, Witness)> {
285    if let Some(found) = find_pr_clause(num_vars, clauses, alpha) {
286        return Some(found);
287    }
288    let c: Vec<Lit> = alpha.iter().map(|l| l.negated()).collect();
289    for sigma in generators {
290        let witness = Witness::Substitution(sigma.extended(num_vars));
291        if is_pr(num_vars, clauses, &c, &witness) {
292            return Some((c, witness));
293        }
294    }
295    None
296}
297
298#[cfg(test)]
299#[path = "../../logicaffeine_tests/unit/logicaffeine_proof/sdcl/tests.rs"]
300mod tests;
301
302#[cfg(test)]
303#[path = "../../logicaffeine_tests/unit/logicaffeine_proof/sdcl/root_propagation.rs"]
304mod root_propagation;