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;