logicaffeine_proof/families.rs
1//! Parametric generators for symmetry-rich SAT families — the canonical hard cases where
2//! symmetry breaking earns its keep. They are programmatic (reproducible, offline, parametric)
3//! rather than vendored `.cnf` files, and each is pinned to its known verdict so the solver and
4//! the certified pipeline can be tested against ground truth.
5
6use crate::cdcl::Lit;
7use crate::dimacs::DimacsCnf;
8
9/// The known verdict of a generated instance, for test oracles.
10#[derive(Clone, Copy, Debug, PartialEq, Eq)]
11pub enum ExpectedVerdict {
12 Sat,
13 Unsat,
14}
15
16/// The pigeonhole principle PHP(n): `n` pigeons into `n-1` holes — unsatisfiable, and the
17/// textbook symmetry / resolution-hard family (any resolution refutation is exponential, while
18/// breaking the `S_n × S_{n-1}` symmetry collapses it). The variable for "pigeon `p` sits in
19/// hole `h`" lives at index `p*(n-1) + h`, so pigeons index rows and holes index columns.
20pub fn php(n: usize) -> (DimacsCnf, ExpectedVerdict) {
21 let holes = n.saturating_sub(1);
22 let num_vars = n * holes;
23 let var = |p: usize, h: usize| Lit::pos((p * holes + h) as u32);
24 let mut clauses: Vec<Vec<Lit>> = Vec::new();
25 // Each pigeon occupies at least one hole (an empty disjunction when holes == 0).
26 for p in 0..n {
27 clauses.push((0..holes).map(|h| var(p, h)).collect());
28 }
29 // No two pigeons share a hole.
30 for h in 0..holes {
31 for p in 0..n {
32 for q in (p + 1)..n {
33 clauses.push(vec![var(p, h).negated(), var(q, h).negated()]);
34 }
35 }
36 }
37 (DimacsCnf { num_vars, clauses }, ExpectedVerdict::Unsat)
38}
39
40/// **Coupled exactly-one + parity** — a scalable MIXED family that needs BOTH structures at once. The
41/// selectors `x₀…x_{n-1}` are constrained to *exactly one* true (an at-most-one clique + an at-least-one
42/// clause — a cardinality covering) AND to *even* total parity `⊕ xᵢ = 0` (a GF(2) system, encoded by a
43/// width-3 prefix-XOR chain with auxiliaries `sᵢ = ⊕_{j≤i} xⱼ` plus the unit `s_{n-1} = 0`). Exactly-one
44/// forces an ODD selector count, the parity forces EVEN — **UNSAT**, yet neither substructure alone is
45/// (the parity chain is satisfiable, exactly-one is satisfiable). The canonical shape for the fused
46/// parity+cardinality route ([`crate::lyapunov::fused_parity_cardinality_decide`]); `2n` variables.
47pub fn parity_exactly_one(n: usize) -> (DimacsCnf, ExpectedVerdict) {
48 assert!(n >= 2, "need at least two selectors");
49 let x = |i: usize| i as u32; // selectors 0..n-1
50 let s = |i: usize| (n + i) as u32; // prefix-XOR auxiliaries n..2n-1
51 let mut clauses: Vec<Vec<Lit>> = Vec::new();
52 // exactly-one of the selectors: at-least-one ∨, then pairwise at-most-one.
53 clauses.push((0..n).map(|i| Lit::pos(x(i))).collect());
54 for i in 0..n {
55 for j in (i + 1)..n {
56 clauses.push(vec![Lit::neg(x(i)), Lit::neg(x(j))]);
57 }
58 }
59 // Prefix-XOR chain: s₀ = x₀, sᵢ = s_{i-1} ⊕ xᵢ, s_{n-1} = 0 — each a small XOR gadget.
60 let gadget = |vars: &[u32], out: &mut Vec<Vec<Lit>>| {
61 let k = vars.len();
62 for mask in 0u32..(1 << k) {
63 if mask.count_ones() % 2 == 1 {
64 out.push(
65 (0..k)
66 .map(|t| Lit::new(vars[t], (mask >> t) & 1 == 0))
67 .collect(),
68 );
69 }
70 }
71 };
72 gadget(&[s(0), x(0)], &mut clauses);
73 for i in 1..n {
74 gadget(&[s(i), s(i - 1), x(i)], &mut clauses);
75 }
76 clauses.push(vec![Lit::neg(s(n - 1))]);
77 (
78 DimacsCnf {
79 num_vars: 2 * n,
80 clauses,
81 },
82 ExpectedVerdict::Unsat,
83 )
84}
85
86/// Graph `k`-coloring of the complete graph `K_n` — the canonical *color-permutation* symmetry
87/// family (the color group `S_k` acts, on top of the vertex group `S_n`). It is unsatisfiable
88/// exactly when `k < n` (a clique of size `n` needs `n` colors). The variable "vertex `v` takes
89/// color `c`" lives at index `v*k + c`.
90pub fn clique_coloring(n: usize, k: usize) -> (DimacsCnf, ExpectedVerdict) {
91 let num_vars = n * k;
92 let var = |v: usize, c: usize| Lit::pos((v * k + c) as u32);
93 let mut clauses: Vec<Vec<Lit>> = Vec::new();
94 // Every vertex takes at least one color.
95 for v in 0..n {
96 clauses.push((0..k).map(|c| var(v, c)).collect());
97 }
98 // Adjacent vertices (every pair, in K_n) must differ in color.
99 for u in 0..n {
100 for w in (u + 1)..n {
101 for c in 0..k {
102 clauses.push(vec![var(u, c).negated(), var(w, c).negated()]);
103 }
104 }
105 }
106 let verdict = if k < n {
107 ExpectedVerdict::Unsat
108 } else {
109 ExpectedVerdict::Sat
110 };
111 (DimacsCnf { num_vars, clauses }, verdict)
112}
113
114/// The mutilated chessboard: an `n×n` board with two OPPOSITE corners removed, asking for a perfect
115/// domino tiling. Every domino covers one black and one white square, but the two removed corners
116/// share a colour (for even `n`), so the black/white counts differ by two and no tiling exists —
117/// UNSAT, and a textbook resolution-exponential family. The infeasibility is a bipartite-matching
118/// (Hall) obstruction, which our covering route certifies in polynomial time. Variables are dominoes
119/// (grid edges between adjacent surviving squares); each surviving square must be covered by exactly
120/// one. `n` must be even (so the parity argument bites).
121pub fn mutilated_chessboard(n: usize) -> (DimacsCnf, ExpectedVerdict) {
122 assert!(
123 n >= 4 && n % 2 == 0,
124 "the parity argument needs an even board ≥ 4"
125 );
126 let removed = |r: usize, c: usize| (r == 0 && c == 0) || (r == n - 1 && c == n - 1);
127 let sq = |r: usize, c: usize| r * n + c;
128 // Edges: horizontal (r,c)–(r,c+1) and vertical (r,c)–(r+1,c), both endpoints surviving.
129 let mut edges: Vec<(usize, usize)> = Vec::new();
130 for r in 0..n {
131 for c in 0..n {
132 if removed(r, c) {
133 continue;
134 }
135 if c + 1 < n && !removed(r, c + 1) {
136 edges.push((sq(r, c), sq(r, c + 1)));
137 }
138 if r + 1 < n && !removed(r + 1, c) {
139 edges.push((sq(r, c), sq(r + 1, c)));
140 }
141 }
142 }
143 let num_vars = edges.len();
144 let mut incident: std::collections::HashMap<usize, Vec<usize>> =
145 std::collections::HashMap::new();
146 for (e, &(a, b)) in edges.iter().enumerate() {
147 incident.entry(a).or_default().push(e);
148 incident.entry(b).or_default().push(e);
149 }
150 let mut clauses: Vec<Vec<Lit>> = Vec::new();
151 for r in 0..n {
152 for c in 0..n {
153 if removed(r, c) {
154 continue;
155 }
156 let inc = incident.get(&sq(r, c)).cloned().unwrap_or_default();
157 clauses.push(inc.iter().map(|&e| Lit::pos(e as u32)).collect()); // covered ≥ once
158 for i in 0..inc.len() {
159 for j in (i + 1)..inc.len() {
160 clauses.push(vec![
161 Lit::pos(inc[i] as u32).negated(),
162 Lit::pos(inc[j] as u32).negated(),
163 ]); // ≤ once
164 }
165 }
166 }
167 }
168 (DimacsCnf { num_vars, clauses }, ExpectedVerdict::Unsat)
169}
170
171/// The linear ordering principle GT(n): no finite strict total order lacks a maximal element — yet
172/// this formula asserts exactly that, so it is UNSAT. `x[i][j]` (index `i*n + j`) reads "i < j".
173/// Antisymmetry + totality + transitivity force a linear order, and the "every element has a greater
174/// one" clauses then contradict finiteness. A canonical resolution-hard family — it stresses the
175/// CDCL core / cutting-plane reasoning rather than a matching or parity specialist.
176pub fn ordering_principle(n: usize) -> (DimacsCnf, ExpectedVerdict) {
177 assert!(n >= 2);
178 let var = |i: usize, j: usize| Lit::pos((i * n + j) as u32);
179 let num_vars = n * n;
180 let mut clauses: Vec<Vec<Lit>> = Vec::new();
181 for i in 0..n {
182 for j in (i + 1)..n {
183 clauses.push(vec![var(i, j), var(j, i)]); // totality
184 clauses.push(vec![var(i, j).negated(), var(j, i).negated()]); // antisymmetry
185 }
186 }
187 for i in 0..n {
188 for j in 0..n {
189 for k in 0..n {
190 if i != j && j != k && i != k {
191 clauses.push(vec![var(i, j).negated(), var(j, k).negated(), var(i, k)]);
192 // transitivity
193 }
194 }
195 }
196 }
197 for i in 0..n {
198 clauses.push((0..n).filter(|&j| j != i).map(|j| var(i, j)).collect()); // i has a greater element
199 }
200 (DimacsCnf { num_vars, clauses }, ExpectedVerdict::Unsat)
201}
202
203/// A random 3-SAT instance: `num_clauses` clauses of three distinct variables with random signs,
204/// over `vars` variables, from a seeded SplitMix64 stream (reproducible — no wall-clock). Near the
205/// clause/variable ratio 4.26 these are the canonical *hard, non-symmetric* benchmarks — the
206/// general-instance control where raw CDCL quality (not symmetry breaking) decides the race.
207pub fn random_3sat(vars: usize, num_clauses: usize, seed: u64) -> DimacsCnf {
208 let mut state = seed;
209 let mut next = move || {
210 state = state.wrapping_add(0x9E3779B97F4A7C15);
211 let mut z = state;
212 z = (z ^ (z >> 30)).wrapping_mul(0xBF58476D1CE4E5B9);
213 z = (z ^ (z >> 27)).wrapping_mul(0x94D049BB133111EB);
214 z ^ (z >> 31)
215 };
216 let mut clauses: Vec<Vec<Lit>> = Vec::with_capacity(num_clauses);
217 while clauses.len() < num_clauses {
218 let mut vs: Vec<u32> = Vec::with_capacity(3);
219 while vs.len() < 3 {
220 let v = (next() as usize % vars) as u32;
221 if !vs.contains(&v) {
222 vs.push(v);
223 }
224 }
225 clauses.push(vs.iter().map(|&v| Lit::new(v, next() & 1 == 0)).collect());
226 }
227 DimacsCnf {
228 num_vars: vars,
229 clauses,
230 }
231}
232
233/// A random **k-SAT** instance: `num_clauses` clauses of `k` distinct variables with random signs, over
234/// `vars` variables, from a seeded SplitMix64 stream (reproducible — no wall-clock). Generalizes
235/// [`random_3sat`]. The satisfiability threshold climbs with `k` roughly as `α_k ≈ 2ᵏ ln 2` (≈ 4.27 for
236/// k=3, ≈ 9.93 for k=4, ≈ 21.1 for k=5). Requires `k ≤ vars`.
237pub fn random_ksat(k: usize, vars: usize, num_clauses: usize, seed: u64) -> DimacsCnf {
238 let mut state = seed;
239 let mut next = move || {
240 state = state.wrapping_add(0x9E3779B97F4A7C15);
241 let mut z = state;
242 z = (z ^ (z >> 30)).wrapping_mul(0xBF58476D1CE4E5B9);
243 z = (z ^ (z >> 27)).wrapping_mul(0x94D049BB133111EB);
244 z ^ (z >> 31)
245 };
246 let mut clauses: Vec<Vec<Lit>> = Vec::with_capacity(num_clauses);
247 while clauses.len() < num_clauses {
248 let mut vs: Vec<u32> = Vec::with_capacity(k);
249 while vs.len() < k {
250 let v = (next() as usize % vars) as u32;
251 if !vs.contains(&v) {
252 vs.push(v);
253 }
254 }
255 clauses.push(vs.iter().map(|&v| Lit::new(v, next() & 1 == 0)).collect());
256 }
257 DimacsCnf {
258 num_vars: vars,
259 clauses,
260 }
261}
262
263/// The CNF clauses encoding the parity constraint `v0 ⊕ v1 ⊕ … = rhs` over any arity (forbid every
264/// wrong-parity assignment of the listed variables — `2^{|vs|-1}` clauses, each of width `|vs|`).
265fn xor_clauses(vs: &[u32], rhs: bool) -> Vec<Vec<Lit>> {
266 let mut out = Vec::new();
267 for mask in 0u32..(1 << vs.len()) {
268 let odd = mask.count_ones() % 2 == 1;
269 if odd != rhs {
270 // Forbid this assignment: a literal is true exactly when it differs from the mask bit.
271 out.push(
272 vs.iter()
273 .enumerate()
274 .map(|(i, &v)| Lit::new(v, (mask >> i) & 1 == 0))
275 .collect(),
276 );
277 }
278 }
279 out
280}
281
282/// Fold a freshly sampled `k`-subset's coefficient row into the running GF(2) echelon basis (rows keyed
283/// by pivot = least set variable). Returns `true` and extends the basis if the row is linearly
284/// independent of those seen so far, `false` if it lies in their span. This is the rank meter that lets
285/// [`random_kxor`] build a *guaranteed*-inconsistent system rather than a merely-probable one.
286fn gf2_absorb(basis: &mut std::collections::HashMap<u32, Vec<u32>>, vars: &[u32]) -> bool {
287 let mut row: std::collections::BTreeSet<u32> = vars.iter().copied().collect();
288 while let Some(&pivot) = row.iter().next() {
289 match basis.get(&pivot) {
290 Some(b) => {
291 for &v in b {
292 if !row.remove(&v) {
293 row.insert(v); // symmetric difference: row ⊕ basis[pivot]
294 }
295 }
296 }
297 None => {
298 basis.insert(pivot, row.iter().copied().collect());
299 return true;
300 }
301 }
302 }
303 false
304}
305
306/// A **guaranteed-unsatisfiable** random **k-XOR** (parity) system over `n` variables: at least `m`
307/// equations of `k` distinct variables, all consistent with a planted assignment `p` except one whose
308/// right-hand side is flipped. Generalizes [`parity_unsat`] (the `k = 3` case).
309///
310/// The flip alone does **not** force inconsistency — it does so only once the flipped row lies in the
311/// span of the others, which a naive "flip the last equation" does not guarantee near `m ≈ n` (it
312/// silently yields *satisfiable* instances). So we build the consistent rows until the coefficient
313/// matrix reaches its **maximum achievable GF(2) rank** (`n` for odd `k`; `n − 1` for even `k`, whose
314/// even-weight rows can never span the all-ones functional) and *at least* `m` rows total, then append
315/// one more equation with a flipped right-hand side. At maximal rank that final row is redundant, so the
316/// system's solution set — `{p}` for odd `k`, `{p, p̄}` for even `k` — is pinned, and *every* pinned
317/// solution violates the flipped row: **the system is inconsistent by construction**, for any seed.
318/// Full-rank `k`-XOR above the XOR-SAT threshold is also exponentially hard for resolution
319/// (Ben-Sasson–Wigderson 2001) — hence for every CDCL solver — yet linear for Gaussian elimination over
320/// GF(2). Each equation expands to `2^{k-1}` width-`k` clauses, so keep `k` modest. `m` is a floor on the
321/// equation count (full rank may need a few more). Returns the XOR equations and the equisatisfiable CNF.
322pub fn random_kxor(
323 k: usize,
324 n: usize,
325 m: usize,
326 seed: u64,
327) -> (Vec<crate::xorsat::XorEquation>, DimacsCnf) {
328 assert!((1..=n).contains(&k) && m >= 1, "need 1 ≤ k ≤ n and m ≥ 1");
329 let mut state = seed;
330 let mut next = move || {
331 state = state.wrapping_add(0x9E3779B97F4A7C15);
332 let mut z = state;
333 z = (z ^ (z >> 30)).wrapping_mul(0xBF58476D1CE4E5B9);
334 z = (z ^ (z >> 27)).wrapping_mul(0x94D049BB133111EB);
335 z ^ (z >> 31)
336 };
337 let planted: Vec<bool> = (0..n).map(|_| next() & 1 == 0).collect();
338 let mut draw = || {
339 let mut vs: Vec<u32> = Vec::with_capacity(k);
340 while vs.len() < k {
341 let v = (next() as usize % n) as u32;
342 if !vs.contains(&v) {
343 vs.push(v);
344 }
345 }
346 vs
347 };
348 let consistent_rhs = |vs: &[u32]| vs.iter().fold(false, |a, &v| a ^ planted[v as usize]);
349
350 // Phase 1: consistent rows until the coefficient matrix is at maximal rank AND there are ≥ m of them.
351 let target_rank = if k % 2 == 1 { n } else { n.saturating_sub(1) };
352 let cap = 8 * n + 64; // generous guard; random k-subsets reach maximal rank far inside this.
353 let mut basis: std::collections::HashMap<u32, Vec<u32>> = std::collections::HashMap::new();
354 let mut rows: Vec<(Vec<u32>, bool)> = Vec::new();
355 let mut rank = 0usize;
356 while (rank < target_rank || rows.len() < m) && rows.len() < cap {
357 let vs = draw();
358 if gf2_absorb(&mut basis, &vs) {
359 rank += 1;
360 }
361 let rhs = consistent_rhs(&vs);
362 rows.push((vs, rhs));
363 }
364 // Phase 2: one more equation, right-hand side FLIPPED. At maximal rank it is redundant, so the pinned
365 // solution set is unchanged by it — yet no pinned solution satisfies it ⇒ the system is UNSAT.
366 let vs = draw();
367 let rhs = !consistent_rhs(&vs);
368 rows.push((vs, rhs));
369
370 let mut eqs = Vec::new();
371 let mut clauses = Vec::new();
372 for (vs, rhs) in &rows {
373 eqs.push(crate::xorsat::XorEquation::new(
374 vs.iter().map(|&v| v as usize).collect::<Vec<_>>(),
375 *rhs,
376 ));
377 clauses.extend(xor_clauses(vs, *rhs));
378 }
379 (
380 eqs,
381 DimacsCnf {
382 num_vars: n,
383 clauses,
384 },
385 )
386}
387
388/// A **guaranteed-unsatisfiable** random 3-XOR (parity) system — the `k = 3` case of [`random_kxor`]:
389/// at least `m` 3-XOR equations over `n` variables, all consistent with a planted assignment except one
390/// flipped row, built up to maximal GF(2) rank so the inconsistency holds for *any* seed (see
391/// [`random_kxor`] for why the naive single flip does not suffice). Full-rank 3-XOR above the XOR-SAT
392/// threshold is **exponentially hard for resolution** (Ben-Sasson–Wigderson 2001), hence for every CDCL
393/// solver — yet linear for Gaussian elimination over GF(2). Returns the XOR equations (for
394/// [`crate::xorsat`]) and the equisatisfiable CNF (for a resolution solver).
395pub fn parity_unsat(n: usize, m: usize, seed: u64) -> (Vec<crate::xorsat::XorEquation>, DimacsCnf) {
396 random_kxor(3, n, m, seed)
397}
398
399/// A random 3-regular graph on `n` (even) vertices via the configuration model with self-loop /
400/// multi-edge rejection — an expander with high probability, which is what makes the Tseitin
401/// formula on it *exponentially* hard for resolution (Urquhart 1987; Ben-Sasson–Wigderson 2001).
402fn random_3regular(n: usize, seed: u64) -> Vec<(usize, usize)> {
403 let mut state = seed ^ 0x9E3779B97F4A7C15;
404 let mut next = move || {
405 state = state.wrapping_add(0x9E3779B97F4A7C15);
406 let mut z = state;
407 z = (z ^ (z >> 30)).wrapping_mul(0xBF58476D1CE4E5B9);
408 z = (z ^ (z >> 27)).wrapping_mul(0x94D049BB133111EB);
409 z ^ (z >> 31)
410 };
411 for _ in 0..4000 {
412 let mut stubs: Vec<usize> = (0..n).flat_map(|v| [v, v, v]).collect();
413 for i in (1..stubs.len()).rev() {
414 let j = (next() as usize) % (i + 1);
415 stubs.swap(i, j);
416 }
417 let mut edges = Vec::new();
418 let mut seen = std::collections::HashSet::new();
419 let mut ok = true;
420 for c in stubs.chunks(2) {
421 let (a, b) = (c[0].min(c[1]), c[0].max(c[1]));
422 if a == b || !seen.insert((a, b)) {
423 ok = false;
424 break;
425 }
426 edges.push((a, b));
427 }
428 if ok {
429 return edges;
430 }
431 }
432 panic!("could not build a simple 3-regular graph on {n} vertices");
433}
434
435/// The **Tseitin formula on a random 3-regular expander** with odd total charge — UNSATISFIABLE,
436/// exponentially hard for resolution (so every CDCL solver blows up), yet solved in polynomial time
437/// by Gaussian elimination over GF(2). A *non-pigeonhole* hard family: the hardness is parity /
438/// graph expansion, not covering symmetry. One Boolean per edge; per vertex, the XOR of its incident
439/// edges equals that vertex's charge (vertex 0 charged, the rest not — an odd sum, hence
440/// inconsistent). Returns the XOR system (for [`crate::xorsat`]) and the equisatisfiable CNF.
441pub fn tseitin_expander(
442 n: usize,
443 seed: u64,
444) -> (Vec<crate::xorsat::XorEquation>, DimacsCnf, ExpectedVerdict) {
445 assert!(
446 n % 2 == 0 && n >= 4,
447 "a 3-regular graph needs an even vertex count ≥ 4"
448 );
449 let edges = random_3regular(n, seed);
450 let m = edges.len();
451 let mut incident: Vec<Vec<usize>> = vec![Vec::new(); n];
452 for (e, &(a, b)) in edges.iter().enumerate() {
453 incident[a].push(e);
454 incident[b].push(e);
455 }
456 let mut eqs = Vec::new();
457 let mut clauses = Vec::new();
458 for v in 0..n {
459 let inc = &incident[v];
460 let r = v == 0; // odd total charge ⇒ UNSAT
461 eqs.push(crate::xorsat::XorEquation::new(inc.clone(), r));
462 let d = inc.len();
463 for mask in 0u32..(1u32 << d) {
464 if ((mask.count_ones() % 2) == 1) != r {
465 clauses.push(
466 (0..d)
467 .map(|i| Lit::new(inc[i] as u32, (mask >> i) & 1 == 0))
468 .collect(),
469 );
470 }
471 }
472 }
473 (
474 eqs,
475 DimacsCnf {
476 num_vars: m,
477 clauses,
478 },
479 ExpectedVerdict::Unsat,
480 )
481}
482
483/// The **Tseitin formula on a `w × n` grid** with odd total charge — UNSATISFIABLE, and the sharpest
484/// indictment of resolution search there is. A grid has treewidth exactly `w` (a fixed constant,
485/// independent of the length `n`), so a POLYNOMIAL-size, bounded-width resolution refutation provably
486/// EXISTS. Yet CDCL solvers without Gaussian reasoning blow up on the parity regardless — they cannot
487/// find the short proof that is known to exist — while Gaussian elimination over GF(2) decides it in
488/// near-linear time. One Boolean per grid edge; per vertex, the XOR of its incident edges equals its
489/// charge (vertex 0 charged, the rest not — an odd sum, hence inconsistent). Returns the XOR system
490/// (for [`crate::xorsat`]) and the equisatisfiable CNF.
491pub fn grid_tseitin(
492 w: usize,
493 n: usize,
494) -> (Vec<crate::xorsat::XorEquation>, DimacsCnf, ExpectedVerdict) {
495 assert!(w >= 2 && n >= 2, "a grid needs both dimensions ≥ 2");
496 let vid = |i: usize, j: usize| i * n + j;
497 let mut incident: Vec<Vec<usize>> = vec![Vec::new(); w * n];
498 let mut num_edges = 0usize;
499 for i in 0..w {
500 for j in 0..n {
501 let v = vid(i, j);
502 if j + 1 < n {
503 let e = num_edges;
504 num_edges += 1;
505 incident[v].push(e);
506 incident[vid(i, j + 1)].push(e);
507 }
508 if i + 1 < w {
509 let e = num_edges;
510 num_edges += 1;
511 incident[v].push(e);
512 incident[vid(i + 1, j)].push(e);
513 }
514 }
515 }
516 let mut eqs = Vec::new();
517 let mut clauses = Vec::new();
518 for v in 0..(w * n) {
519 let inc = &incident[v];
520 let r = v == 0; // odd total charge ⇒ UNSAT
521 eqs.push(crate::xorsat::XorEquation::new(inc.clone(), r));
522 let d = inc.len();
523 for mask in 0u32..(1u32 << d) {
524 if ((mask.count_ones() % 2) == 1) != r {
525 clauses.push(
526 (0..d)
527 .map(|i| Lit::new(inc[i] as u32, (mask >> i) & 1 == 0))
528 .collect(),
529 );
530 }
531 }
532 }
533 (
534 eqs,
535 DimacsCnf {
536 num_vars: num_edges,
537 clauses,
538 },
539 ExpectedVerdict::Unsat,
540 )
541}
542
543/// The **mod-`p` Tseitin obstruction on a random 3-regular expander** — the parity crush carried to
544/// every prime. Each edge carries a `GF(p)` flow variable; orient each edge and impose, at every
545/// vertex, the signed divergence `Σ_out − Σ_in ≡ charge (mod p)`. Summing all vertices telescopes the
546/// edge variables to `0`, so the system is inconsistent exactly when the total charge `≢ 0 (mod p)`.
547/// We charge two vertices (total `2`): **inconsistent over `GF(p)` for every odd prime `p`, yet
548/// consistent over `GF(2)`** (`2 ≡ 0`) — a family the parity cut is structurally blind to, decided
549/// instantly by Gaussian elimination over the *right* `GF(p)`, and (on an expander) exponentially hard
550/// for resolution. Returns the `GF(p)` system (for [`crate::modp`]), the equisatisfiable one-hot
551/// Boolean CNF (for resolution solvers), and the `GF(p)` verdict.
552pub fn mod_p_tseitin_expander(
553 n: usize,
554 p: u64,
555 seed: u64,
556) -> (Vec<crate::modp::ModpEquation>, DimacsCnf, ExpectedVerdict) {
557 assert!(
558 p >= 3,
559 "the mod-p obstruction needs an odd prime (p=2 is the parity case, consistent here)"
560 );
561 mod_tseitin_expander_core(n, p, seed)
562}
563
564/// The **composite-modulus** sibling of [`mod_p_tseitin_expander`]: the same total-charge-2 divergence
565/// obstruction over `ℤ/m` for a squarefree composite `m` (e.g. `m = 6`), with a mixed-radix one-hot
566/// Boolean encoding (`m` values per edge). By CRT `ℤ/m ≅ ∏ GF(pᵢ)`, so the system is inconsistent over
567/// `ℤ/m` exactly when it is inconsistent over some prime factor — total charge `2 ≢ 0 (mod m)` for any
568/// `m ≥ 3` that does not divide `2` — and [`crate::modm::solve`] decides it through that factor with a
569/// solver-free re-checkable certificate ([`crate::modm::is_refutation`]). This drives the **ring**
570/// route (`ℤ/m` Gaussian via CRT), not the prime-field route, on a CNF that resolution still walls on.
571pub fn mod_m_tseitin_expander(
572 n: usize,
573 m: u64,
574 seed: u64,
575) -> (Vec<crate::modp::ModpEquation>, DimacsCnf, ExpectedVerdict) {
576 assert!(
577 m >= 3,
578 "the composite obstruction needs a modulus ≥ 3 (m=2 is the parity case, consistent here)"
579 );
580 mod_tseitin_expander_core(n, m, seed)
581}
582
583/// Shared construction for the total-charge-2 divergence obstruction over `ℤ/modulus` on a random
584/// 3-regular expander, used by both the prime-field ([`mod_p_tseitin_expander`]) and composite-ring
585/// ([`mod_m_tseitin_expander`]) families. Returns the `ℤ/modulus` divergence system, the equisatisfiable
586/// one-hot Boolean CNF (`modulus` values per edge), and the UNSAT verdict. Charging two vertices makes
587/// the total `2`, which is `≢ 0 (mod modulus)` for every `modulus ≥ 3` yet `≡ 0 (mod 2)` — so the parity
588/// cut is blind to it and only Gaussian elimination over the right characteristic decides it.
589fn mod_tseitin_expander_core(
590 n: usize,
591 modulus: u64,
592 seed: u64,
593) -> (Vec<crate::modp::ModpEquation>, DimacsCnf, ExpectedVerdict) {
594 use crate::cdcl::Lit;
595 use crate::modp::ModpEquation;
596 assert!(
597 n % 2 == 0 && n >= 4,
598 "a 3-regular graph needs an even vertex count ≥ 4"
599 );
600 let edges = random_3regular(n, seed); // each (a, b) with a < b; orient a → b (tail a, head b)
601 let ne = edges.len();
602 let charge = |v: usize| u64::from(v == 0 || v == 1); // total charge 2: ≢0 mod modulus (≥3), ≡0 mod 2
603
604 // The ℤ/modulus divergence system: +x_e at the tail, −x_e (= (modulus−1)·x_e) at the head.
605 let mut eqs: Vec<ModpEquation> = Vec::new();
606 for v in 0..n {
607 let mut coeffs: Vec<(usize, u64)> = Vec::new();
608 for (e, &(a, b)) in edges.iter().enumerate() {
609 if a == v {
610 coeffs.push((e, 1));
611 } else if b == v {
612 coeffs.push((e, modulus - 1));
613 }
614 }
615 eqs.push(ModpEquation::new(coeffs, charge(v)));
616 }
617
618 // The equisatisfiable Boolean CNF: one-hot bit b(e, val) = "edge e takes value val" (var e*modulus+val).
619 let bvar = |e: usize, val: u64| (e * modulus as usize + val as usize) as u32;
620 let mut clauses: Vec<Vec<Lit>> = Vec::new();
621 for e in 0..ne {
622 clauses.push((0..modulus).map(|val| Lit::pos(bvar(e, val))).collect()); // ≥1 value
623 for v1 in 0..modulus {
624 for v2 in (v1 + 1)..modulus {
625 clauses.push(vec![Lit::neg(bvar(e, v1)), Lit::neg(bvar(e, v2))]);
626 // ≤1 value
627 }
628 }
629 }
630 // Per vertex, forbid every assignment of its incident edge-values whose signed sum ≢ charge.
631 for v in 0..n {
632 let incident: Vec<(usize, i64)> = edges
633 .iter()
634 .enumerate()
635 .filter_map(|(e, &(a, b))| {
636 if a == v {
637 Some((e, 1i64))
638 } else if b == v {
639 Some((e, -1i64))
640 } else {
641 None
642 }
643 })
644 .collect();
645 let d = incident.len();
646 let want = charge(v) as i64;
647 let pi = modulus as i64;
648 for idx in 0..modulus.pow(d as u32) {
649 let mut x = idx;
650 let mut combo = vec![0u64; d];
651 for slot in combo.iter_mut() {
652 *slot = x % modulus;
653 x /= modulus;
654 }
655 let s = incident
656 .iter()
657 .zip(&combo)
658 .fold(0i64, |acc, (&(_, sign), &val)| acc + sign * val as i64);
659 if (s.rem_euclid(pi)) != (want.rem_euclid(pi)) {
660 clauses.push(
661 incident
662 .iter()
663 .zip(&combo)
664 .map(|(&(e, _), &val)| Lit::neg(bvar(e, val)))
665 .collect(),
666 );
667 }
668 }
669 }
670
671 (
672 eqs,
673 DimacsCnf {
674 num_vars: ne * modulus as usize,
675 clauses,
676 },
677 ExpectedVerdict::Unsat,
678 )
679}
680
681/// A **satisfiable** sibling of [`mod_p_tseitin_expander`] over the same 3-regular graph and the same
682/// one-hot Boolean encoding, but with a charge distribution whose total `≡ 0 (mod p)`. The divergence
683/// system `Σ_out x − Σ_in x ≡ charge(v)` is consistent exactly when the charges sum to zero (summing all
684/// vertex equations telescopes the left side to `0`), so this instance is SAT — the control for the GF(p)
685/// route's model-returning path. Charge: `+1` at vertex 0, `−1 (= p−1)` at vertex 1, zero elsewhere.
686pub fn mod_p_consistent_onehot(
687 n: usize,
688 p: u64,
689 seed: u64,
690) -> (Vec<crate::modp::ModpEquation>, DimacsCnf, ExpectedVerdict) {
691 use crate::cdcl::Lit;
692 use crate::modp::ModpEquation;
693 assert!(
694 n % 2 == 0 && n >= 4,
695 "a 3-regular graph needs an even vertex count ≥ 4"
696 );
697 assert!(p >= 3, "the mod-p one-hot encoding needs an odd prime");
698 let edges = random_3regular(n, seed);
699 let ne = edges.len();
700 let charge = |v: usize| -> u64 {
701 match v {
702 0 => 1,
703 1 => p - 1,
704 _ => 0,
705 }
706 }; // total charge ≡ 0 (mod p) ⟹ consistent
707
708 let mut eqs: Vec<ModpEquation> = Vec::new();
709 for v in 0..n {
710 let mut coeffs: Vec<(usize, u64)> = Vec::new();
711 for (e, &(a, b)) in edges.iter().enumerate() {
712 if a == v {
713 coeffs.push((e, 1));
714 } else if b == v {
715 coeffs.push((e, p - 1));
716 }
717 }
718 eqs.push(ModpEquation::new(coeffs, charge(v)));
719 }
720
721 let bvar = |e: usize, val: u64| (e * p as usize + val as usize) as u32;
722 let mut clauses: Vec<Vec<Lit>> = Vec::new();
723 for e in 0..ne {
724 clauses.push((0..p).map(|val| Lit::pos(bvar(e, val))).collect());
725 for v1 in 0..p {
726 for v2 in (v1 + 1)..p {
727 clauses.push(vec![Lit::neg(bvar(e, v1)), Lit::neg(bvar(e, v2))]);
728 }
729 }
730 }
731 for v in 0..n {
732 let incident: Vec<(usize, i64)> = edges
733 .iter()
734 .enumerate()
735 .filter_map(|(e, &(a, b))| {
736 if a == v {
737 Some((e, 1i64))
738 } else if b == v {
739 Some((e, -1i64))
740 } else {
741 None
742 }
743 })
744 .collect();
745 let d = incident.len();
746 let want = charge(v) as i64;
747 let pi = p as i64;
748 for idx in 0..p.pow(d as u32) {
749 let mut x = idx;
750 let mut combo = vec![0u64; d];
751 for slot in combo.iter_mut() {
752 *slot = x % p;
753 x /= p;
754 }
755 let s = incident
756 .iter()
757 .zip(&combo)
758 .fold(0i64, |acc, (&(_, sign), &val)| acc + sign * val as i64);
759 if (s.rem_euclid(pi)) != (want.rem_euclid(pi)) {
760 clauses.push(
761 incident
762 .iter()
763 .zip(&combo)
764 .map(|(&(e, _), &val)| Lit::neg(bvar(e, val)))
765 .collect(),
766 );
767 }
768 }
769 }
770
771 (
772 eqs,
773 DimacsCnf {
774 num_vars: ne * p as usize,
775 clauses,
776 },
777 ExpectedVerdict::Sat,
778 )
779}
780
781/// The **first-moment (counting) upper bound** on the random k-SAT satisfiability threshold:
782/// `α*(k) = ln 2 / ln(2ᵏ / (2ᵏ − 1))`. Above this clause density the expected number of satisfying
783/// assignments `E[X] = 2ⁿ(1 − 2⁻ᵏ)^{αn} = (2·(1 − 2⁻ᵏ)^α)ⁿ` has per-variable base `< 1`, so `E[X] → 0`
784/// and the instance is UNSAT with high probability (Markov) — a **rigorous** upper bound on the true
785/// threshold, exact and closed-form (no sampling). The sequence climbs as `2ᵏ ln 2 − (ln 2)/2`,
786/// asymptotically **doubling per k**: `2.41, 5.19, 10.74, 21.83, 44.02, …` for `k = 2, 3, 4, 5, 6, …`.
787/// The *true* thresholds (≈ 1, 4.27, 9.93, 21.1, …) lie below it; the gap → ½ as k → ∞ (the difference
788/// between the first-moment bound `2ᵏln2 − ½ln2` and the sharp value `2ᵏln2 − (1+ln2)/2`).
789pub fn ksat_threshold_first_moment_upper(k: u32) -> f64 {
790 let pow = (1u64 << k) as f64;
791 std::f64::consts::LN_2 / (pow / (pow - 1.0)).ln()
792}
793
794/// All `q`-element subsets of `{0, …, n−1}` in lexicographic order (the standard combinatorial
795/// odometer). Returns empty when `q > n`. Used to build the hyperedge / clique families below; keep
796/// `n` and `q` small, the count is `C(n, q)`.
797fn combinations(n: usize, q: usize) -> Vec<Vec<usize>> {
798 let mut out = Vec::new();
799 if q == 0 || q > n {
800 return out;
801 }
802 let mut idx: Vec<usize> = (0..q).collect();
803 loop {
804 out.push(idx.clone());
805 let mut i = q;
806 loop {
807 if i == 0 {
808 return out;
809 }
810 i -= 1;
811 if idx[i] != i + n - q {
812 break;
813 }
814 }
815 idx[i] += 1;
816 for j in (i + 1)..q {
817 idx[j] = idx[j - 1] + 1;
818 }
819 }
820}
821
822/// The **weak pigeonhole principle** `PHP^{holes}_{pigeons}`: `pigeons` pigeons into `holes` holes —
823/// unsatisfiable exactly when `pigeons > holes`. Generalizes [`php`] (which is the tight
824/// `holes = pigeons − 1` case) to any hole count, including the *weak* regime (`holes = 2·pigeons`,
825/// `pigeons²`, …) used to probe how far symmetry breaking scales as the holes-to-pigeons ratio grows.
826/// Same variable layout as [`php`] — "pigeon `p` in hole `h`" at index `p*holes + h` — so
827/// `weak_php(n, n−1)` is byte-for-byte `php(n)`.
828pub fn weak_php(pigeons: usize, holes: usize) -> (DimacsCnf, ExpectedVerdict) {
829 let num_vars = pigeons * holes;
830 let var = |p: usize, h: usize| Lit::pos((p * holes + h) as u32);
831 let mut clauses: Vec<Vec<Lit>> = Vec::new();
832 for p in 0..pigeons {
833 clauses.push((0..holes).map(|h| var(p, h)).collect()); // each pigeon in ≥ 1 hole
834 }
835 for h in 0..holes {
836 for p in 0..pigeons {
837 for q in (p + 1)..pigeons {
838 clauses.push(vec![var(p, h).negated(), var(q, h).negated()]); // ≤ 1 pigeon per hole
839 }
840 }
841 }
842 let verdict = if pigeons > holes {
843 ExpectedVerdict::Unsat
844 } else {
845 ExpectedVerdict::Sat
846 };
847 (DimacsCnf { num_vars, clauses }, verdict)
848}
849
850/// The **functional pigeonhole principle** FPHP(n): `php(n)` strengthened so each pigeon sits in *at
851/// most* one hole (the placement is a function, not a relation). Adds the "no pigeon in two holes"
852/// clauses on top of PHP; still UNSAT, still `S_n × S_{n−1}`-symmetric, and the standard strengthening
853/// used to check that symmetry breaking survives the extra functional clauses. Same layout as [`php`].
854pub fn functional_php(n: usize) -> (DimacsCnf, ExpectedVerdict) {
855 let holes = n.saturating_sub(1);
856 let (mut cnf, _) = php(n);
857 let var = |p: usize, h: usize| Lit::pos((p * holes + h) as u32);
858 for p in 0..n {
859 for h1 in 0..holes {
860 for h2 in (h1 + 1)..holes {
861 cnf.clauses
862 .push(vec![var(p, h1).negated(), var(p, h2).negated()]); // ≤ 1 hole per pigeon
863 }
864 }
865 }
866 (cnf, ExpectedVerdict::Unsat)
867}
868
869/// The **onto (bijective) pigeonhole principle** onto-FPHP(n): `functional_php(n)` further forced to
870/// be *onto* — every hole receives at least one pigeon. The placement is now a bijection `n → n−1`,
871/// which cannot exist; UNSAT. This is the hardest standard PHP variant for symmetry reasoning (it pins
872/// both the pigeon and the hole side), and the maximal clause set over the shared [`php`] layout.
873pub fn onto_php(n: usize) -> (DimacsCnf, ExpectedVerdict) {
874 let holes = n.saturating_sub(1);
875 let (mut cnf, _) = functional_php(n);
876 let var = |p: usize, h: usize| Lit::pos((p * holes + h) as u32);
877 for h in 0..holes {
878 cnf.clauses.push((0..n).map(|p| var(p, h)).collect()); // each hole gets ≥ 1 pigeon (onto)
879 }
880 (cnf, ExpectedVerdict::Unsat)
881}
882
883/// The **modular counting principle** `Count_q(n)`: can the `n`-element set `{0,…,n−1}` be exactly
884/// partitioned into blocks of size `q`? A Boolean per `q`-subset (hyperedge); clauses force every
885/// element to lie in ≥ 1 chosen block and forbid any two *overlapping* blocks — so the chosen blocks
886/// are a perfect `q`-cover (an exact partition). That exists iff `q ∣ n`, hence the formula is
887/// **UNSAT exactly when `q ∤ n`**. This is the canonical *modular* family — the obstruction is a
888/// counting argument mod `q` that resolution cannot make at low width (Ajtai; Beame–Pitassi), the
889/// natural target of the GF(q) / mod-`m` rung. `q = 2` is perfect matching on the complete graph `K_n`
890/// (UNSAT for odd `n`). The hyperedge count is `C(n, q)`, so keep `n`, `q` small.
891pub fn mod_counting(n: usize, q: usize) -> (DimacsCnf, ExpectedVerdict) {
892 assert!(q >= 2 && n >= q, "need a block size q ≥ 2 with n ≥ q");
893 let edges = combinations(n, q);
894 let num_vars = edges.len();
895 let mut incident: Vec<Vec<usize>> = vec![Vec::new(); n];
896 for (e, edge) in edges.iter().enumerate() {
897 for &v in edge {
898 incident[v].push(e);
899 }
900 }
901 let mut clauses: Vec<Vec<Lit>> = Vec::new();
902 for inc in &incident {
903 clauses.push(inc.iter().map(|&e| Lit::pos(e as u32)).collect()); // every element covered ≥ once
904 }
905 for e in 0..edges.len() {
906 for f in (e + 1)..edges.len() {
907 if edges[e].iter().any(|v| edges[f].contains(v)) {
908 clauses.push(vec![Lit::neg(e as u32), Lit::neg(f as u32)]); // overlapping blocks are exclusive
909 }
910 }
911 }
912 let verdict = if n % q == 0 {
913 ExpectedVerdict::Sat
914 } else {
915 ExpectedVerdict::Unsat
916 };
917 (DimacsCnf { num_vars, clauses }, verdict)
918}
919
920/// The exactly-one groups of [`mod_counting`]'s **linear encoding**: for each point, the variables of
921/// its covering clause — the incident `q`-subsets, in the same variable order as [`mod_counting`].
922/// Feed to `polycalc::exactly_one_linear_generators` for the degree-1 point generators plus overlap
923/// pairs (the encoding the modular-counting degree lower bounds are stated against).
924pub fn mod_counting_groups(n: usize, q: usize) -> Vec<Vec<u32>> {
925 let (cnf, _) = mod_counting(n, q);
926 cnf.clauses
927 .iter()
928 .filter(|c| c.iter().all(|l| l.is_positive()))
929 .map(|c| c.iter().map(|l| l.var()).collect())
930 .collect()
931}
932
933/// The edge layout of [`mod_counting`]: variable `e` is the `q`-subset `mod_counting_edges(n, q)[e]`
934/// of the point set `{0,…,n−1}` — the map a witness-support predicate needs to read a monomial as a
935/// set of blocks.
936pub fn mod_counting_edges(n: usize, q: usize) -> Vec<Vec<usize>> {
937 combinations(n, q)
938}
939
940/// The known two-colour Ramsey numbers `R(s, t)` for the small `(s, t)` we can actually build CNFs for
941/// (symmetric: `R(s, t) = R(t, s)`); `None` when the value is still an open problem. `R(s, t)` is the
942/// least `n` such that every red/blue colouring of `K_n`'s edges contains a red `K_s` or a blue `K_t`.
943pub fn ramsey_number(s: usize, t: usize) -> Option<usize> {
944 let (a, b) = (s.min(t), s.max(t));
945 match (a, b) {
946 (1, _) => Some(1),
947 (2, b) => Some(b),
948 (3, 3) => Some(6),
949 (3, 4) => Some(9),
950 (3, 5) => Some(14),
951 (3, 6) => Some(18),
952 (3, 7) => Some(23),
953 (3, 8) => Some(28),
954 (3, 9) => Some(36),
955 (4, 4) => Some(18),
956 (4, 5) => Some(25),
957 _ => None,
958 }
959}
960
961/// The **Ramsey formula** `Ramsey(s, t; n)`: 2-colour the edges of the complete graph `K_n` (one
962/// Boolean per edge — true = red, false = blue) avoiding every red `K_s` and every blue `K_t`. For each
963/// `s`-clique a clause forbids all its edges being red; for each `t`-clique a clause forbids all blue.
964/// Such a colouring exists iff `n < R(s, t)`, so the formula is **UNSAT exactly when `n ≥ R(s, t)`**.
965/// A genuinely different geometry from pigeonhole/parity — clique structure, not covering or counting —
966/// and a classic CDCL stress family (`Ramsey(3,3;6)` is the smallest UNSAT case). Panics for `(s, t)`
967/// whose Ramsey number is unknown (so the verdict is never guessed); see [`ramsey_number`].
968pub fn ramsey(s: usize, t: usize, n: usize) -> (DimacsCnf, ExpectedVerdict) {
969 assert!(s >= 2 && t >= 2 && n >= 2);
970 let r = ramsey_number(s, t).expect("Ramsey number R(s,t) must be known to pin the verdict");
971 let mut edge_id = std::collections::HashMap::new();
972 for (e, pair) in combinations(n, 2).iter().enumerate() {
973 edge_id.insert((pair[0], pair[1]), e as u32);
974 }
975 let num_vars = edge_id.len();
976 let mut clauses: Vec<Vec<Lit>> = Vec::new();
977 let clique_edges = |clique: &[usize]| -> Vec<u32> {
978 combinations(clique.len(), 2)
979 .iter()
980 .map(|p| edge_id[&(clique[p[0]], clique[p[1]])])
981 .collect()
982 };
983 for clique in combinations(n, s) {
984 clauses.push(clique_edges(&clique).into_iter().map(Lit::neg).collect());
985 // not all red
986 }
987 for clique in combinations(n, t) {
988 clauses.push(clique_edges(&clique).into_iter().map(Lit::pos).collect());
989 // not all blue
990 }
991 let verdict = if n >= r {
992 ExpectedVerdict::Unsat
993 } else {
994 ExpectedVerdict::Sat
995 };
996 (DimacsCnf { num_vars, clauses }, verdict)
997}
998
999/// The **pebbling contradiction** on the pyramid DAG of the given `height` — the canonical resolution
1000/// *space* family (Ben-Sasson–Wigderson; Nordström). The pyramid has rows `0..=height` with row `r`
1001/// holding `r+1` nodes; each node `(r, i)` for `r < height` has the two predecessors `(r+1, i)` and
1002/// `(r+1, i+1)` below it. One Boolean per node "is pebbled": every source (bottom row) is asserted
1003/// pebbled (unit), pebbling propagates up (`pebbled(a) ∧ pebbled(b) → pebbled(parent)`), and the apex
1004/// `(0,0)` is asserted *un*pebbled — a contradiction, so UNSAT. Refutation size is linear (unit
1005/// propagation alone closes it), but refuting it in small *space* provably is not — the axis pigeonhole
1006/// and parity do not touch.
1007pub fn pebbling_pyramid(height: usize) -> (DimacsCnf, ExpectedVerdict) {
1008 let node = |r: usize, i: usize| (r * (r + 1) / 2 + i) as u32; // triangular id, apex = node(0,0) = 0
1009 let num_vars = (height + 1) * (height + 2) / 2;
1010 let mut clauses: Vec<Vec<Lit>> = Vec::new();
1011 for i in 0..=height {
1012 clauses.push(vec![Lit::pos(node(height, i))]); // sources (bottom row) are pebbled
1013 }
1014 for r in 0..height {
1015 for i in 0..=r {
1016 clauses.push(vec![
1017 Lit::neg(node(r + 1, i)),
1018 Lit::neg(node(r + 1, i + 1)),
1019 Lit::pos(node(r, i)),
1020 ]); // both children pebbled ⇒ this node pebbled
1021 }
1022 }
1023 clauses.push(vec![Lit::neg(node(0, 0))]); // the apex is asserted unpebbled — the contradiction
1024 (DimacsCnf { num_vars, clauses }, ExpectedVerdict::Unsat)
1025}
1026
1027#[cfg(test)]
1028#[path = "../../logicaffeine_tests/unit/logicaffeine_proof/families/tests.rs"]
1029mod tests;