Skip to main content

logicaffeine_proof/
xor_drat.rs

1//! The CNF→GF(2) bridge: compile a Gaussian (XOR linear-dependency) refutation into a **strict DRAT
2//! proof** that an external checker (`drat-trim`) accepts.
3//!
4//! Our parity route refutes Tseitin/XOR formulas by linear algebra: it finds a set `S` of recovered
5//! XOR equations whose GF(2) sum telescopes to `0 = 1` ([`crate::xorsat::solve`] → `Unsat(S)`). That
6//! certificate is sound and re-checkable *algebraically* — but it is not the Boolean clausal proof
7//! the competition toolchain consumes. This module closes that gap.
8//!
9//! **The construction (why each emitted line is RUP).** Every equation in `S` is encoded in the CNF
10//! by its full parity gadget (the `2^{k-1}` clauses forbidding wrong-parity assignments). The
11//! conjunction of the gadgets of `S` is unsatisfiable (their linear combination is `0 = 1`), so the
12//! empty clause is derivable from them by *resolution*. We produce that derivation by Davis–Putnam
13//! variable elimination over the support, in min-degree order, emitting each resolvent as a proof
14//! line. A resolvent of two clauses already in the formula is **RUP** (reverse-unit-propagation)
15//! against that formula, and we only ever grow the formula — so every line checks, and the final
16//! line is the empty clause. The proof is polynomial when the elimination keeps clauses narrow
17//! (bounded cut-/tree-width); it can blow up on high-expansion instances, which is the honest limit
18//! of the resolution route (the polynomial extension-variable construction is the next rung).
19//!
20//! Soundness is independent of how the equations were recovered: the gadget clauses we resolve over
21//! are entailed by the CNF, and the emitted proof is checked by `drat-trim` against the *original*
22//! formula, so a faulty recovery cannot produce an accepted proof.
23
24use std::collections::{BTreeSet, HashSet};
25
26use crate::cdcl::Lit;
27use crate::xorsat::XorEquation;
28
29/// The full parity gadget of `eq`: one clause per wrong-parity assignment of its variables. These are
30/// exactly the CNF clauses a Tseitin/XOR encoding carries for the constraint.
31pub fn gadget_clauses(eq: &XorEquation) -> Vec<Vec<Lit>> {
32    let k = eq.vars.len();
33    let mut out = Vec::new();
34    for mask in 0u32..(1u32 << k) {
35        // `mask` is the assignment (bit i = value of vars[i]); it violates the parity when its
36        // popcount-parity disagrees with the rhs. The forbidding clause is false under `mask`.
37        if (mask.count_ones() % 2 == 1) != eq.rhs {
38            out.push(
39                (0..k)
40                    .map(|i| Lit::new(eq.vars[i] as u32, (mask >> i) & 1 == 0))
41                    .collect(),
42            );
43        }
44    }
45    out
46}
47
48/// Canonical key for a clause (sorted, deduped literal codes), for dedup/subsumption-free bookkeeping.
49fn key(c: &[Lit]) -> Vec<u32> {
50    let mut k: Vec<u32> = c
51        .iter()
52        .map(|l| l.var() * 2 + u32::from(!l.is_positive()))
53        .collect();
54    k.sort_unstable();
55    k.dedup();
56    k
57}
58
59/// Resolve `a` and `b` on variable `v` (which appears positively in one, negatively in the other).
60/// Returns the resolvent with `v` removed, or `None` if it is a tautology (contains `x` and `¬x`).
61fn resolve(a: &[Lit], b: &[Lit], v: u32) -> Option<Vec<Lit>> {
62    let mut seen: std::collections::HashMap<u32, bool> = std::collections::HashMap::new();
63    for l in a.iter().chain(b.iter()) {
64        if l.var() == v {
65            continue;
66        }
67        if let Some(&prev) = seen.get(&l.var()) {
68            if prev != l.is_positive() {
69                return None; // x and ¬x ⇒ tautology
70            }
71        } else {
72            seen.insert(l.var(), l.is_positive());
73        }
74    }
75    let mut out: Vec<Lit> = seen
76        .into_iter()
77        .map(|(var, pos)| Lit::new(var, pos))
78        .collect();
79    out.sort_by_key(|l| l.var() * 2 + u32::from(!l.is_positive()));
80    Some(out)
81}
82
83/// Derive the empty clause from an unsatisfiable clause set by Davis–Putnam variable elimination,
84/// returning the ordered list of resolvents (each RUP against the original set plus the earlier
85/// resolvents). Eliminates in min-degree order to keep intermediate clauses small. Returns `None`
86/// only if the input was not actually unsatisfiable (no refutation exists).
87/// Resolvent budget: the resolution route is polynomial only when the elimination keeps clauses
88/// narrow; past this many emitted clauses we declare the route blown (fail-closed) rather than hang.
89const RESOLUTION_BUDGET: usize = 40_000;
90/// Raw-work budget: a single elimination can attempt `|pos|·|neg|` resolutions, which explodes long
91/// before the emitted-clause budget trips (most attempts are duplicates/tautologies). Cap the attempts
92/// so a blown instance bails in seconds rather than minutes.
93const RESOLUTION_WORK_BUDGET: u64 = 4_000_000;
94
95fn resolution_refutation(support: &[Vec<Lit>]) -> Option<Vec<Vec<Lit>>> {
96    // Active working set, deduped; and the set of every clause key already in play (so a resolvent we
97    // re-derive is not emitted twice).
98    let mut active: Vec<Vec<Lit>> = Vec::new();
99    let mut present: HashSet<Vec<u32>> = HashSet::new();
100    for c in support {
101        let k = key(c);
102        if present.insert(k) {
103            active.push({
104                let mut c = c.clone();
105                c.sort_by_key(|l| l.var() * 2 + u32::from(!l.is_positive()));
106                c.dedup();
107                c
108            });
109        }
110    }
111    let mut emitted: Vec<Vec<Lit>> = Vec::new();
112    let mut work: u64 = 0;
113    if active.iter().any(|c| c.is_empty()) {
114        emitted.push(Vec::new());
115        return Some(emitted);
116    }
117
118    loop {
119        let vars: BTreeSet<u32> = active
120            .iter()
121            .flat_map(|c| c.iter().map(|l| l.var()))
122            .collect();
123        if vars.is_empty() {
124            return None; // nothing left to eliminate but no empty clause: input was satisfiable
125        }
126        // Min-product (min-fill proxy): eliminate the variable whose resolution fan-out `|pos|·|neg|`
127        // is smallest — that bounds both the work and the number of new clauses, keeping the proof as
128        // narrow as the instance's structure allows (the lever before extension variables).
129        let v = *vars
130            .iter()
131            .min_by_key(|&&v| {
132                let (mut p, mut n) = (0usize, 0usize);
133                for c in &active {
134                    match c.iter().find(|l| l.var() == v) {
135                        Some(l) if l.is_positive() => p += 1,
136                        Some(_) => n += 1,
137                        None => {}
138                    }
139                }
140                p * n
141            })
142            .unwrap();
143
144        let mut pos: Vec<Vec<Lit>> = Vec::new();
145        let mut neg: Vec<Vec<Lit>> = Vec::new();
146        let mut rest: Vec<Vec<Lit>> = Vec::new();
147        for c in active.drain(..) {
148            match c.iter().find(|l| l.var() == v) {
149                Some(l) if l.is_positive() => pos.push(c),
150                Some(_) => neg.push(c),
151                None => rest.push(c),
152            }
153        }
154
155        let mut next = rest;
156        for cp in &pos {
157            for cn in &neg {
158                work += 1;
159                if work > RESOLUTION_WORK_BUDGET {
160                    return None; // raw-work blowup: bail fast, fail-closed.
161                }
162                let Some(r) = resolve(cp, cn, v) else {
163                    continue;
164                };
165                if r.is_empty() {
166                    emitted.push(Vec::new());
167                    return Some(emitted);
168                }
169                let k = key(&r);
170                if present.insert(k) {
171                    emitted.push(r.clone());
172                    next.push(r);
173                    if emitted.len() > RESOLUTION_BUDGET {
174                        return None; // the resolution route blew up on this instance's width.
175                    }
176                }
177            }
178        }
179        active = next;
180        // The clauses mentioning `v` are now eliminated; they stay in the DRAT formula (we never
181        // delete), so every future resolvent remains RUP against the growing database.
182    }
183}
184
185/// Compile the GF(2) linear-dependency refutation `refutation` (equation indices whose XOR is `0=1`,
186/// from [`crate::xorsat::solve`]) into a DRAT proof: the ordered resolvent clauses, ending in the
187/// empty clause. Pair these with the original CNF for [`crate::rup::check_refutation`] or `drat-trim`.
188pub fn emit_xor_drat(equations: &[XorEquation], refutation: &[usize]) -> Option<Vec<Vec<Lit>>> {
189    let mut support: Vec<Vec<Lit>> = Vec::new();
190    for &i in refutation {
191        support.extend(gadget_clauses(&equations[i]));
192    }
193    resolution_refutation(&support)
194}
195
196/// Resolution-refute the sub-CNF confined to the `support` variables — the convention-agnostic bridge.
197/// The emitted clauses are resolvents of *real* CNF clauses, so each is RUP against the original
198/// formula by construction and a `drat-trim` check holds. `None` if that sub-CNF is not UNSAT (so the
199/// caller's algebraic verdict could not be reproduced clausally — a fail-closed signal).
200pub fn emit_drat_over_support(
201    clauses: &[Vec<Lit>],
202    support: &BTreeSet<u32>,
203) -> Option<Vec<Vec<Lit>>> {
204    let sub: Vec<Vec<Lit>> = clauses
205        .iter()
206        .filter(|c| c.iter().all(|l| support.contains(&l.var())))
207        .cloned()
208        .collect();
209    resolution_refutation(&sub)
210}
211
212/// The CNF→GF(p) bridge: compile a *modular* (mod-p / counting) UNSAT verdict into a strict DRAT
213/// proof. We recover the one-hot modular system from `clauses`, solve it over the prime field, and —
214/// on UNSAT — resolution-refute the sub-CNF confined to the one-hot bits of the involved groups. That
215/// sub-CNF (the forbidden-tuple gadgets of the combination's equations together with their groups'
216/// at-least-one/at-most-one clauses) is unsatisfiable, so DP elimination over those Boolean variables
217/// yields the empty clause, every line RUP against the original CNF. `None` if the formula is not a
218/// recoverable mod-p encoding or its modular system is satisfiable.
219pub fn emit_modp_drat(num_vars: usize, clauses: &[Vec<Lit>]) -> Option<Vec<Vec<Lit>>> {
220    let rec = crate::modp::recover_from_cnf(num_vars, clauses)?;
221    if !crate::modp::is_prime(rec.modulus) {
222        return None; // composite moduli go through the ring engine; the prime field is the bridge here.
223    }
224    let combo = match crate::modp::solve(&rec.equations, rec.num_vars, rec.modulus) {
225        crate::modp::ModpOutcome::Unsat(combo) => combo,
226        crate::modp::ModpOutcome::Sat(_) => return None,
227    };
228    // The groups (modular variables) that actually appear in the refuting linear combination.
229    let mut groups_involved: BTreeSet<usize> = BTreeSet::new();
230    for &(eq_idx, mult) in &combo {
231        if mult % rec.modulus == 0 {
232            continue;
233        }
234        for &(g, _) in &rec.equations[eq_idx].coeffs {
235            groups_involved.insert(g);
236        }
237    }
238    let support: BTreeSet<u32> = groups_involved
239        .iter()
240        .flat_map(|&g| rec.groups[g].iter().copied())
241        .collect();
242    emit_drat_over_support(clauses, &support)
243}
244
245#[cfg(test)]
246#[path = "../../logicaffeine_tests/unit/logicaffeine_proof/xor_drat/tests.rs"]
247mod tests;