Skip to main content

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;