logicaffeine_proof/sym_dynamic.rs
1//! Dynamic symmetry breaking — **Symmetric Explanation Learning** (SEL), the in-search tier.
2//!
3//! Static symmetry breaking adds predicates up front (Phase 1). SEL is reactive: it watches what
4//! the solver *learns* and multiplies each learned clause by the formula's symmetry group, so the
5//! search never has to re-derive the symmetric twin of a lemma it already paid for. On a
6//! symmetry-rich UNSAT instance that is the whole game — the exponential blow-up resolution suffers
7//! is exactly the repeated rediscovery of symmetric variants.
8//!
9//! **The certification is free.** If a learned clause `C` is RUP w.r.t. the database and `σ` is an
10//! automorphism of that database, then `σ(C)` is RUP too: apply `σ` to `C`'s unit-propagation
11//! refutation and every clause it touches maps back into `σ(F) = F`. So a symmetric clause enters
12//! the proof as a plain [`ProofStep::Rup`] — DRAT/LRAT-checkable, no PR witness needed. We add a
13//! `σ(C)` only after re-confirming it is RUP against the *current* database (`rup::is_rup`), so
14//! the procedure is **fail-closed**: an amplification that does not check is silently dropped, never
15//! trusted.
16//!
17//! The loop alternates a conflict-budgeted solve ([`Solver::solve_budgeted`]) with an amplification
18//! pass over the round's learned clauses, accumulating a single RUP refutation that
19//! [`crate::pr::check_pr_refutation_fast`] verifies against the original formula alone.
20
21use std::collections::HashSet;
22
23use crate::cdcl::{BudgetedResult, Lit, Solver};
24use crate::proof::ProofStep;
25use crate::symmetry_detect::find_generators;
26
27/// The result of an SEL refutation attempt.
28#[derive(Clone, Debug)]
29pub enum SelOutcome {
30 /// Refuted, with a checkable RUP proof, the total conflicts spent, and how many clauses were
31 /// added by symmetric amplification (the lever's footprint).
32 Unsat {
33 steps: Vec<ProofStep>,
34 conflicts: u64,
35 amplified: usize,
36 },
37 /// Satisfiable, with a model.
38 Sat(Vec<bool>),
39 /// Gave up within the round/budget bounds without a verdict (the procedure is deliberately
40 /// incomplete — it never returns a wrong answer, only an honest "don't know").
41 Unknown { conflicts: u64 },
42}
43
44/// Canonical clause key (sorted, deduped literal codes) for the seen-set.
45fn canon(c: &[Lit]) -> Vec<u32> {
46 let mut k: Vec<u32> = c
47 .iter()
48 .map(|l| l.var() * 2 + u32::from(!l.is_positive()))
49 .collect();
50 k.sort_unstable();
51 k.dedup();
52 k
53}
54
55/// Add `x` as a RUP step iff it is new and genuinely RUP against the current database (fail-closed).
56fn try_add(
57 num_vars: usize,
58 db: &mut Vec<Vec<Lit>>,
59 steps: &mut Vec<ProofStep>,
60 seen: &mut HashSet<Vec<u32>>,
61 x: Vec<Lit>,
62) -> bool {
63 let key = canon(&x);
64 if seen.contains(&key) {
65 return false;
66 }
67 if crate::rup::is_rup(num_vars, db, &x) {
68 seen.insert(key);
69 db.push(x.clone());
70 steps.push(ProofStep::Rup(x));
71 true
72 } else {
73 false
74 }
75}
76
77/// Refute `clauses` with Symmetric Explanation Learning, or report SAT / Unknown. The conflict
78/// budget per round and the round cap bound the work; symmetric amplification is what makes the
79/// total conflict count collapse on symmetry-rich instances.
80pub fn sel_refute(num_vars: usize, clauses: &[Vec<Lit>]) -> SelOutcome {
81 let gens = find_generators(num_vars, clauses);
82 let mut db: Vec<Vec<Lit>> = clauses.to_vec();
83 let mut steps: Vec<ProofStep> = Vec::new();
84 let mut seen: HashSet<Vec<u32>> = db.iter().map(|c| canon(c)).collect();
85 let mut total_conflicts = 0u64;
86 let mut amplified = 0usize;
87 let mut budget = 64u64;
88 const MAX_ROUNDS: usize = 4000;
89
90 for _round in 0..MAX_ROUNDS {
91 if crate::rup::is_rup(num_vars, &db, &[]) {
92 break;
93 }
94 let mut solver = Solver::new(num_vars);
95 // Keep every learned clause for the round so the RUP trace we lift is complete; reduction
96 // would drop clauses the closing chain may depend on (the budget keeps the set small).
97 solver.set_reduce(false);
98 for c in &db {
99 solver.add_clause(c.clone());
100 }
101 let res = solver.solve_budgeted(budget);
102 total_conflicts += solver.conflicts();
103
104 match res {
105 BudgetedResult::Sat(model) => return SelOutcome::Sat(model),
106 BudgetedResult::Unsat => {
107 // Refuted within budget — append the closing learned clauses and finish.
108 let learned: Vec<Vec<Lit>> =
109 solver.learned().iter().map(|l| l.lits.clone()).collect();
110 for c in learned {
111 try_add(num_vars, &mut db, &mut steps, &mut seen, c);
112 }
113 break;
114 }
115 BudgetedResult::Budget => {
116 let learned: Vec<Vec<Lit>> =
117 solver.learned().iter().map(|l| l.lits.clone()).collect();
118 let mut progress = false;
119 for c in learned {
120 if try_add(num_vars, &mut db, &mut steps, &mut seen, c.clone()) {
121 progress = true;
122 }
123 // The orbit of `c` under the generators — each image is RUP when σ is still a
124 // symmetry of the current database, and dropped otherwise (fail-closed).
125 for g in &gens {
126 let image = g.apply_clause(&c);
127 if try_add(num_vars, &mut db, &mut steps, &mut seen, image) {
128 amplified += 1;
129 progress = true;
130 }
131 }
132 }
133 if !progress {
134 // No new lemmas at this budget — give the solver more rope before conceding.
135 budget = budget.saturating_mul(2);
136 if budget > 1_000_000 {
137 break;
138 }
139 }
140 }
141 }
142 }
143
144 if crate::pr::check_pr_refutation_fast(num_vars, clauses, &steps) {
145 SelOutcome::Unsat {
146 steps,
147 conflicts: total_conflicts,
148 amplified,
149 }
150 } else {
151 SelOutcome::Unknown {
152 conflicts: total_conflicts,
153 }
154 }
155}
156
157#[cfg(test)]
158#[path = "../../logicaffeine_tests/unit/logicaffeine_proof/sym_dynamic/tests.rs"]
159mod tests;