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;