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;