Skip to main content

logicaffeine_proof/
sos.rs

1//! **Sum-of-Squares / Positivstellensatz refutation over ℚ — kept EXACT** (no SDP, no floating point)
2//! by the LP slice of the cone. True SoS is a semidefinite program over the reals; that would forfeit
3//! our certified guarantee. Instead we take the *diagonal* (fixed-square-basis) Positivstellensatz, which
4//! is an exact rational linear program: a CNF is lifted to degree-2 pseudo-Boolean inequalities and the
5//! lift is refuted by exact Fourier–Motzkin / Farkas elimination.
6//!
7//! The lift, over variables `xᵢ` and the products `zᵢⱼ = xᵢ·xⱼ` (i < j):
8//! - **box**: `0 ≤ xᵢ ≤ 1`;
9//! - **McCormick envelope** of each product: `zᵢⱼ ≥ 0`, `zᵢⱼ ≤ xᵢ`, `zᵢⱼ ≤ xⱼ`, `zᵢⱼ ≥ xᵢ+xⱼ−1`
10//!   (the exact integral hull of `zᵢⱼ = xᵢ ∧ xⱼ`);
11//! - **clauses**: `Σ val(lit) ≥ 1`, `val(x)=x`, `val(¬x)=1−x`;
12//! - **Sherali–Adams products**: each clause times `xⱼ` and times `1−xⱼ` (the degree-2 lift);
13//! - **squares**: `(xᵢ−xⱼ)² ≥ 0` and `(1−xᵢ−xⱼ)² ≥ 0` — the genuine sum-of-squares terms, the
14//!   ordered-field content that Nullstellensatz/Polynomial-Calculus (equality-only over GF(2)) cannot
15//!   express.
16//!
17//! **Soundness**: every constraint holds at every Boolean assignment, so a Boolean model of the CNF is a
18//! feasible point of the lift; therefore an *infeasible* lift (a Farkas refutation) certifies the CNF
19//! UNSAT. The elimination is exact `i128` and **fail-closed under load**: it declines (reports no
20//! refutation) the moment a coefficient would exceed `MAG_CAP` or the row count would exceed
21//! `ROW_CAP`, so it never returns an overflow-corrupted verdict. Incomplete at degree 2 (that is the
22//! whole point of the degree dial), and the square basis is symmetry-reducible — quotient it by the
23//! formula's automorphisms to shrink the LP, the same "symmetry break to uncover more" that collapses
24//! the field cuts and the monomial basis.
25
26use crate::cdcl::Lit;
27use std::collections::BTreeMap;
28
29/// Degree-2 lifts have ≈ n²/2 product variables; Fourier–Motzkin is doubly-exponential in the variable
30/// count, so only small cores are lifted — larger instances decline to the other routes. (A rational
31/// simplex, or the symmetry-reduced LP, is the scaling path.)
32const MAX_VARS: usize = 6;
33/// Decline once the working set grows past this — bounds the elimination's time/space. Genuine
34/// degree-2 refutations of small cores are found in far fewer rows; past this we are in blow-up territory
35/// and decline (soundly) rather than grind.
36const ROW_CAP: usize = 20_000;
37/// Decline once any coefficient would exceed this — keeps every `i128` operation exact (no overflow).
38const MAG_CAP: i128 = 1 << 50;
39
40/// A degree-≤2 multilinear polynomial over the Booleans: constant + Σ aᵢ·xᵢ + Σ bᵢⱼ·xᵢxⱼ (i < j).
41#[derive(Clone, Default)]
42struct Poly {
43    c: i64,
44    lin: BTreeMap<usize, i64>,
45    quad: BTreeMap<(usize, usize), i64>,
46}
47
48impl Poly {
49    fn constant(c: i64) -> Self {
50        Poly {
51            c,
52            ..Default::default()
53        }
54    }
55    fn x(i: usize) -> Self {
56        Poly {
57            lin: BTreeMap::from([(i, 1)]),
58            ..Default::default()
59        }
60    }
61    fn add(&self, o: &Self) -> Self {
62        let mut r = self.clone();
63        r.c += o.c;
64        for (&k, &v) in &o.lin {
65            *r.lin.entry(k).or_insert(0) += v;
66        }
67        for (&k, &v) in &o.quad {
68            *r.quad.entry(k).or_insert(0) += v;
69        }
70        r.prune()
71    }
72    fn neg(&self) -> Self {
73        Poly {
74            c: -self.c,
75            lin: self.lin.iter().map(|(&k, &v)| (k, -v)).collect(),
76            quad: self.quad.iter().map(|(&k, &v)| (k, -v)).collect(),
77        }
78    }
79    fn sub(&self, o: &Self) -> Self {
80        self.add(&o.neg())
81    }
82    fn prune(mut self) -> Self {
83        self.lin.retain(|_, v| *v != 0);
84        self.quad.retain(|_, v| *v != 0);
85        self
86    }
87    /// Multiply two **linear** polynomials (no quadratic part), folding `xᵢ² = xᵢ` (multilinear).
88    fn mul_linear(a: &Self, b: &Self) -> Self {
89        debug_assert!(
90            a.quad.is_empty() && b.quad.is_empty(),
91            "mul_linear needs degree-1 inputs"
92        );
93        let mut r = Poly::constant(a.c * b.c);
94        for (&i, &ai) in &a.lin {
95            *r.lin.entry(i).or_insert(0) += ai * b.c;
96        }
97        for (&j, &bj) in &b.lin {
98            *r.lin.entry(j).or_insert(0) += a.c * bj;
99        }
100        for (&i, &ai) in &a.lin {
101            for (&j, &bj) in &b.lin {
102                if i == j {
103                    *r.lin.entry(i).or_insert(0) += ai * bj; // xᵢ·xᵢ = xᵢ
104                } else {
105                    *r.quad.entry((i.min(j), i.max(j))).or_insert(0) += ai * bj;
106                }
107            }
108        }
109        r.prune()
110    }
111}
112
113/// The value polynomial of a literal: `x` for a positive literal, `1 − x` for a negative one.
114fn lit_value(l: &Lit) -> Poly {
115    let x = Poly::x(l.var() as usize);
116    if l.is_positive() {
117        x
118    } else {
119        Poly::constant(1).sub(&x)
120    }
121}
122
123/// A linear inequality `Σ coeffs·var + constant ≤ 0` over the lifted variables (`xᵢ` and `zᵢⱼ`), carrying
124/// the non-negative combination `prov` of original constraints that produced it.
125#[derive(Clone)]
126struct Row {
127    coeffs: BTreeMap<usize, i128>,
128    constant: i128,
129    prov: BTreeMap<usize, i128>,
130}
131
132impl Row {
133    /// `combined = self·ka + other·kb` (ka, kb ≥ 0), or `None` if any magnitude would exceed [`MAG_CAP`].
134    fn combine(&self, ka: i128, other: &Row, kb: i128) -> Option<Row> {
135        let mut coeffs = BTreeMap::new();
136        let mut acc =
137            |dst: &mut BTreeMap<usize, i128>, src: &BTreeMap<usize, i128>, k: i128| -> Option<()> {
138                for (&v, &c) in src {
139                    let e = dst.entry(v).or_insert(0);
140                    *e = e.checked_add(c.checked_mul(k)?)?;
141                    if e.abs() > MAG_CAP {
142                        return None;
143                    }
144                }
145                Some(())
146            };
147        acc(&mut coeffs, &self.coeffs, ka)?;
148        acc(&mut coeffs, &other.coeffs, kb)?;
149        coeffs.retain(|_, c| *c != 0);
150        let constant = self
151            .constant
152            .checked_mul(ka)?
153            .checked_add(other.constant.checked_mul(kb)?)?;
154        if constant.abs() > MAG_CAP {
155            return None;
156        }
157        let mut prov = BTreeMap::new();
158        acc(&mut prov, &self.prov, ka)?;
159        acc(&mut prov, &other.prov, kb)?;
160        prov.retain(|_, c| *c != 0);
161        Some(Row {
162            coeffs,
163            constant,
164            prov,
165        })
166    }
167}
168
169/// Convert a `Poly` (meaning `poly ≤ 0`) into a lift `Row`, tagged with original-constraint index `idx`.
170/// `zᵢⱼ` gets a stable index above the `xᵢ` block.
171fn poly_to_row(p: &Poly, num_vars: usize, idx: usize) -> Row {
172    let mut coeffs = BTreeMap::new();
173    for (&i, &v) in &p.lin {
174        coeffs.insert(i, v as i128);
175    }
176    for (&(i, j), &v) in &p.quad {
177        coeffs.insert(num_vars + i * num_vars + j, v as i128); // z index, unique for i<j<num_vars
178    }
179    Row {
180        coeffs,
181        constant: p.c as i128,
182        prov: BTreeMap::from([(idx, 1)]),
183    }
184}
185
186/// Push `p ≥ 0` into the lift as the constraint `−p ≤ 0`.
187fn ge0(out: &mut Vec<Poly>, p: Poly) {
188    out.push(p.neg());
189}
190
191/// The polynomials of the degree-2 lift, each meaning `poly ≤ 0`.
192fn lift_polys(num_vars: usize, clauses: &[Vec<Lit>]) -> Vec<Poly> {
193    let mut out: Vec<Poly> = Vec::new();
194    let one = Poly::constant(1);
195    for i in 0..num_vars {
196        ge0(&mut out, Poly::x(i));
197        ge0(&mut out, one.sub(&Poly::x(i)));
198    }
199    for i in 0..num_vars {
200        for j in (i + 1)..num_vars {
201            let z = Poly {
202                quad: BTreeMap::from([((i, j), 1)]),
203                ..Default::default()
204            };
205            let (xi, xj) = (Poly::x(i), Poly::x(j));
206            ge0(&mut out, z.clone());
207            ge0(&mut out, xi.sub(&z));
208            ge0(&mut out, xj.sub(&z));
209            ge0(&mut out, z.sub(&xi).sub(&xj).add(&one));
210            ge0(&mut out, xi.add(&xj).sub(&z).sub(&z)); // (xᵢ−xⱼ)²
211            ge0(&mut out, one.sub(&xi).sub(&xj).add(&z).add(&z)); // (1−xᵢ−xⱼ)²
212        }
213    }
214    for c in clauses {
215        if c.is_empty() {
216            out.push(Poly::constant(1)); // 1 ≤ 0
217            continue;
218        }
219        let mut cl = Poly::constant(-1);
220        for l in c {
221            cl = cl.add(&lit_value(l));
222        }
223        ge0(&mut out, cl.clone());
224        for j in 0..num_vars {
225            ge0(&mut out, Poly::mul_linear(&cl, &Poly::x(j)));
226            ge0(&mut out, Poly::mul_linear(&cl, &one.sub(&Poly::x(j))));
227        }
228    }
229    out
230}
231
232/// Exact Fourier–Motzkin: is `{ rowᵢ ≤ 0 }` infeasible over ℚ? Returns the Farkas multipliers (a
233/// non-negative combination of the original rows summing to a positive constant `≤ 0`) on infeasibility,
234/// or `None` if feasible **or** if the elimination exceeded [`ROW_CAP`]/[`MAG_CAP`] (fail-closed: a
235/// decline is reported as "no refutation found", never a false one).
236fn farkas_refute(rows: Vec<Row>, var_count: usize) -> Option<BTreeMap<usize, i128>> {
237    let contradiction = |rows: &[Row]| -> Option<BTreeMap<usize, i128>> {
238        rows.iter()
239            .find(|r| r.coeffs.is_empty() && r.constant > 0)
240            .map(|r| r.prov.clone())
241    };
242    let mut rows = rows;
243    if let Some(p) = contradiction(&rows) {
244        return Some(p);
245    }
246    for v in 0..var_count {
247        let (mut pos, mut neg, mut next): (Vec<&Row>, Vec<&Row>, Vec<Row>) =
248            (Vec::new(), Vec::new(), Vec::new());
249        for r in &rows {
250            match r.coeffs.get(&v).copied().unwrap_or(0) {
251                c if c > 0 => pos.push(r),
252                c if c < 0 => neg.push(r),
253                _ => next.push(r.clone()),
254            }
255        }
256        for p in &pos {
257            for n in &neg {
258                let pc = p.coeffs[&v];
259                let nc = -n.coeffs[&v];
260                let combined = p.combine(nc, n, pc)?; // None ⟹ magnitude overflow ⟹ decline
261                next.push(combined);
262                if next.len() > ROW_CAP {
263                    return None; // decline rather than blow up
264                }
265            }
266        }
267        rows = next;
268        if let Some(p) = contradiction(&rows) {
269            return Some(p);
270        }
271    }
272    contradiction(&rows)
273}
274
275/// Does a degree-2 Positivstellensatz (diagonal SoS) refutation of the CNF exist over ℚ? Sound: a `true`
276/// result is a certified UNSAT. Declines (false) when no degree-2 refutation exists or the instance
277/// exceeds `MAX_VARS` / the elimination caps.
278pub fn sos_refutes(num_vars: usize, clauses: &[Vec<Lit>]) -> bool {
279    sos_certificate(num_vars, clauses).is_some()
280}
281
282/// The Farkas certificate of a degree-2 SoS refutation: the non-negative multipliers over the lift
283/// constraints whose combination is a positive constant `≤ 0`. `None` if no degree-2 refutation is found.
284/// Re-checkable: combining the lift polynomials with these multipliers yields a bare positive constant.
285pub fn sos_certificate(num_vars: usize, clauses: &[Vec<Lit>]) -> Option<BTreeMap<usize, i128>> {
286    if num_vars > MAX_VARS {
287        return None;
288    }
289    let polys = lift_polys(num_vars, clauses);
290    let rows: Vec<Row> = polys
291        .iter()
292        .enumerate()
293        .map(|(i, p)| poly_to_row(p, num_vars, i))
294        .collect();
295    let var_count = num_vars + num_vars * num_vars; // xᵢ block + zᵢⱼ block (sparse upper indices)
296    farkas_refute(rows, var_count)
297}
298
299/// Independently re-check an SoS Farkas certificate from [`sos_certificate`]: recompute the degree-2
300/// lift from the clauses, combine its polynomials with the certificate's multipliers, and confirm the
301/// result cancels every variable and leaves a strictly positive constant — the self-contained
302/// contradiction `0 < d ≤ 0`. It shares no arithmetic with the Fourier–Motzkin elimination that
303/// produced the certificate, so it is a genuine independent witness of the refutation (the SoS analog
304/// of [`crate::xorsat::is_refutation`]). Fails closed on a negative multiplier, an out-of-range row,
305/// an empty certificate, or any residual variable.
306pub fn check_sos_certificate(
307    num_vars: usize,
308    clauses: &[Vec<Lit>],
309    cert: &BTreeMap<usize, i128>,
310) -> bool {
311    if cert.is_empty() {
312        return false;
313    }
314    let polys = lift_polys(num_vars, clauses);
315    let (mut lin, mut quad) = (
316        BTreeMap::<usize, i128>::new(),
317        BTreeMap::<(usize, usize), i128>::new(),
318    );
319    let mut constant: i128 = 0;
320    for (&i, &mult) in cert {
321        if mult < 0 || i >= polys.len() {
322            return false; // Farkas multipliers are non-negative and index real lift rows.
323        }
324        let p = &polys[i];
325        constant += mult * p.c as i128;
326        for (&v, &c) in &p.lin {
327            *lin.entry(v).or_insert(0) += mult * c as i128;
328        }
329        for (&k, &c) in &p.quad {
330            *quad.entry(k).or_insert(0) += mult * c as i128;
331        }
332    }
333    lin.values().all(|&c| c == 0) && quad.values().all(|&c| c == 0) && constant > 0
334}
335
336#[cfg(test)]
337#[path = "../../logicaffeine_tests/unit/logicaffeine_proof/sos/tests.rs"]
338mod tests;