logicaffeine_proof/hypercube.rs
1//! The Boolean hypercube `{0,1}ⁿ` and its subcube cover — the geometric substrate beneath SAT,
2//! and the executable form of the Lean formalization's `HypercubeSAT`.
3//!
4//! Every clause of a CNF is a **blocker**: the set of corners (vertices) of the hypercube that
5//! *falsify* it. A clause of width `w` forbids exactly the `2^{n-w}` corners that set each of its
6//! literals false — a subcube (a face) of codimension `w`. The whole formula is UNSAT precisely
7//! when its blockers **cover** the hypercube: every one of the `2ⁿ` corners is forbidden by some
8//! clause, so no satisfying assignment escapes. SAT ⟺ some corner has *energy zero* — covered by
9//! no blocker. This is `Pnp.lean`'s `Blocker` / `vertexEnergy` / `CoverUNSAT`, made concrete.
10//!
11//! The point of the representation: the **problem** (solutions = uncovered corners) and the
12//! **rules** (clauses = blockers) live in the *same* world `{0,1}ⁿ`. A clause is not a separate
13//! syntactic object; it is a region of the very space the solutions inhabit. So one group action —
14//! a [`CubeSym`], `Pnp.lean`'s `CubeSymmetry` of coordinate permutations and per-coordinate flips —
15//! moves *both*: it permutes blockers among themselves and permutes corners among themselves, in
16//! lockstep. That is what lets us symmetry-break the rules and the solutions with a single move, and
17//! it is why the cover-totality question (UNSAT) collapses by the order of the symmetry group: a
18//! cover is total iff it covers **one representative per orbit**, not all `2ⁿ` corners.
19//!
20//! Pigeonhole is the canonical instance because we can always build one ([`php_cover`]): `n` pigeons
21//! into `n-1` holes, with the full row×column symmetry group `Sₙ × Sₙ₋₁` acting on the grid of
22//! variables. Here we build the stage, answer the first question — *which corners are we blocking?* —
23//! and then **measure** how far each stacked symmetry collapses the cover-check.
24
25use crate::cdcl::Lit;
26use crate::dimacs::DimacsCnf;
27use crate::proof::Perm;
28use std::collections::{BTreeSet, HashMap};
29
30/// A corner (vertex) of the hypercube `{0,1}ⁿ`: bit `v` holds the value of variable `v`.
31/// Enumeration routines assume `n ≤ 63`; the algebra itself is width-agnostic.
32pub type Corner = u64;
33
34/// A subcube of `{0,1}ⁿ`: the coordinates set in `care` are fixed to the matching bits of `value`;
35/// the rest are free. As a **blocker** it is the footprint of one clause — the corners that falsify
36/// it. (`Pnp.lean`'s `Blocker`, generalized from clean 3-bit faces to any width.)
37#[derive(Clone, Copy, Debug, PartialEq, Eq, PartialOrd, Ord, Hash)]
38pub struct Subcube {
39 pub n: usize,
40 /// Bitmask of the fixed ("cared-about") coordinates — the blocker's support.
41 pub care: u64,
42 /// Required values on the fixed coordinates; bits outside `care` are held at 0.
43 pub value: u64,
44}
45
46impl Subcube {
47 /// The blocker of a clause: the subcube of corners that set *every* literal false. A positive
48 /// literal `xᵥ` is false at `c[v]=0`; a negative literal `¬xᵥ` is false at `c[v]=1`. So `care`
49 /// is the clause's variable set and `value`'s bit `v` is set exactly for the negative literals.
50 pub fn blocker(clause: &[Lit], n: usize) -> Subcube {
51 let mut care = 0u64;
52 let mut value = 0u64;
53 for &lit in clause {
54 let v = lit.var() as u64;
55 care |= 1u64 << v;
56 if !lit.is_positive() {
57 value |= 1u64 << v;
58 }
59 }
60 Subcube { n, care, value }
61 }
62
63 /// Does this subcube contain `corner`? (`Pnp.lean`'s `Blocker.Covers` — is the clause falsified
64 /// at this corner?)
65 #[inline]
66 pub fn covers(&self, corner: Corner) -> bool {
67 (corner & self.care) == self.value
68 }
69
70 /// The number of free coordinates — the subcube's dimension as a face (`n - |support|`).
71 pub fn dimension(&self) -> usize {
72 self.n - self.care.count_ones() as usize
73 }
74
75 /// How many corners this blocker forbids: `2^dimension` (the footprint cardinality).
76 pub fn footprint_card(&self) -> u64 {
77 1u64 << self.dimension()
78 }
79
80 /// Recover the clause this blocker is the footprint of — the inverse of [`Subcube::blocker`].
81 /// A fixed coordinate `v` appears *positively* when `value`'s bit is 0 (the clause is falsified
82 /// at `v=0`) and *negatively* when it is 1. Round-tripping a clause through `blocker` and back is
83 /// the proof that the geometric representation loses nothing.
84 pub fn clause_literals(&self) -> Vec<(usize, bool)> {
85 (0..self.n)
86 .filter(|&v| self.care & (1u64 << v) != 0)
87 .map(|v| (v, self.value & (1u64 << v) == 0))
88 .collect()
89 }
90
91 /// The LP value of this blocker's clause at a fractional point of `[0,1]ⁿ`: `Σ` over literals of
92 /// `x` (positive) or `1−x` (negative). The clause's relaxation is satisfied iff the value is `≥ 1`.
93 /// At the ½-center every literal contributes ½, so the value is `width/2` — satisfied iff width ≥ 2.
94 pub fn clause_lp_value(&self, point: &[f64]) -> f64 {
95 self.clause_literals()
96 .iter()
97 .map(|&(v, positive)| if positive { point[v] } else { 1.0 - point[v] })
98 .sum()
99 }
100
101 /// **Resolve two blockers — the geometry of clause resolution, the engine of "rules beget rules."**
102 /// Two blockers resolve when their fixed coordinates agree everywhere except a single *pivot* where
103 /// they take opposite values (one clause carries the pivot literal, the other its negation, with no
104 /// other clashing literal). The resolvent is the merged blocker with the pivot freed — a *new rule*
105 /// derived from the two neighbors, exactly the Quine–McCluskey adjacency of two implicants. Returns
106 /// `(pivot, resolvent)`, or `None` when there is no single clean pivot (no opposite literal, or a
107 /// second clash making the resolvent a tautology).
108 pub fn resolve(&self, other: &Subcube) -> Option<(usize, Subcube)> {
109 let shared = self.care & other.care;
110 let disagree = shared & (self.value ^ other.value);
111 if disagree.count_ones() != 1 {
112 return None;
113 }
114 let pivot = disagree.trailing_zeros() as usize;
115 let care = (self.care | other.care) & !(1u64 << pivot);
116 let value = (self.value | other.value) & care;
117 Some((
118 pivot,
119 Subcube {
120 n: self.n,
121 care,
122 value,
123 },
124 ))
125 }
126
127 /// Enumerate the blocked corners — the full footprint. Only sensible for small dimension.
128 pub fn footprint(&self) -> Vec<Corner> {
129 let free: Vec<u64> = (0..self.n as u64)
130 .filter(|i| self.care & (1u64 << i) == 0)
131 .collect();
132 let mut out = Vec::with_capacity(1usize << free.len());
133 for mask in 0..(1u64 << free.len()) {
134 let mut c = self.value;
135 for (j, &i) in free.iter().enumerate() {
136 if mask & (1u64 << j) != 0 {
137 c |= 1u64 << i;
138 }
139 }
140 out.push(c);
141 }
142 out
143 }
144}
145
146/// A cover of the hypercube by clause-blockers — the geometric form of a CNF. UNSAT ⟺ the blockers
147/// leave no corner uncovered.
148#[derive(Clone, Debug)]
149pub struct Cover {
150 pub n: usize,
151 pub blockers: Vec<Subcube>,
152}
153
154impl Cover {
155 /// The blocker cover of a CNF: one subcube per clause.
156 pub fn of_cnf(cnf: &DimacsCnf) -> Cover {
157 let n = cnf.num_vars;
158 let blockers = cnf.clauses.iter().map(|c| Subcube::blocker(c, n)).collect();
159 Cover { n, blockers }
160 }
161
162 /// The **energy** of a corner: how many blockers cover it (`Pnp.lean`'s `vertexEnergy`).
163 /// Energy zero ⟺ the corner is a satisfying assignment.
164 pub fn vertex_energy(&self, corner: Corner) -> usize {
165 self.blockers.iter().filter(|b| b.covers(corner)).count()
166 }
167
168 /// Is `corner` forbidden by some clause? (Does it falsify the formula?)
169 pub fn blocks(&self, corner: Corner) -> bool {
170 self.blockers.iter().any(|b| b.covers(corner))
171 }
172
173 /// `Pnp.lean`'s vertex energy classes. **Tight**: covered by exactly one blocker — that blocker is
174 /// *essential* there, deleting it exposes the corner. **Redundant**: two or more cover it, robust
175 /// to dropping one. (Uncovered, energy 0, is a model — [`escaping_corner`](Self::escaping_corner).)
176 pub fn is_tight(&self, corner: Corner) -> bool {
177 self.vertex_energy(corner) == 1
178 }
179
180 /// `Pnp.lean`'s `VertexOverlappedBy`: two or more blockers cover this corner.
181 pub fn is_redundant(&self, corner: Corner) -> bool {
182 self.vertex_energy(corner) >= 2
183 }
184
185 /// The **essential blockers** — the irreducible core of the cover. A blocker is essential when it
186 /// *privately* covers some corner (a tight vertex no other blocker reaches); deleting it would
187 /// break totality. The essential set is the geometric analog of a minimal resolution refutation:
188 /// the rules you cannot drop. (Enumerates footprints — for small covers.)
189 pub fn essential_blockers(&self) -> Vec<usize> {
190 (0..self.blockers.len())
191 .filter(|&i| {
192 self.blockers[i]
193 .footprint()
194 .iter()
195 .any(|&c| self.vertex_energy(c) == 1)
196 })
197 .collect()
198 }
199
200 /// The first corner no blocker reaches — a satisfying assignment of energy zero — or `None`
201 /// when the cover is total. `None` ⟺ the formula is UNSAT. Brute over all `2ⁿ` corners.
202 pub fn escaping_corner(&self) -> Option<Corner> {
203 (0u64..(1u64 << self.n)).find(|&c| !self.blocks(c))
204 }
205
206 /// UNSAT ⟺ the blockers cover **every** corner of the hypercube (`Pnp.lean`'s `HasNoHole`).
207 pub fn is_total(&self) -> bool {
208 self.escaping_corner().is_none()
209 }
210
211 /// The number of satisfying assignments — uncovered corners of energy zero (`solutionCount`).
212 pub fn solution_count(&self) -> u64 {
213 (0u64..(1u64 << self.n))
214 .filter(|&c| !self.blocks(c))
215 .count() as u64
216 }
217
218 /// `Pnp.lean`'s `HasNoHole` (refutation side): the cover is total — no corner escapes.
219 pub fn has_no_hole(&self) -> bool {
220 self.is_total()
221 }
222
223 /// **The ½ key — is the LP relaxation feasible at the symmetric center?** The all-½ point satisfies
224 /// a clause's relaxation (`Σ lits ≥ 1`) iff the clause has width ≥ 2 (each literal contributes ½).
225 /// When *every* blocker has width ≥ 2, the center `½ⁿ` is a feasible fractional point — so the cover
226 /// can be integer-UNSAT while its LP relaxation is satisfiable. That integrality gap, sitting exactly
227 /// at the symmetry-fixed center, is what resolution (which lives at the corners) cannot see and what
228 /// the counting/cutting-planes shadows close.
229 pub fn relaxation_feasible_at_center(&self) -> bool {
230 self.blockers.iter().all(|b| b.care.count_ones() >= 2)
231 }
232
233 /// Generalized counting crush: derive the `O(1)` Hall certificate (`items > slots`) from *any*
234 /// matching-shaped cover — pigeonhole, clique-coloring, anything that symmetry-breaks to the same
235 /// two rule-types — by recovering the bipartite structure. The pigeonhole crush, no longer
236 /// hard-coded to pigeonhole.
237 pub fn counting_refutation(&self) -> Option<crate::pigeonhole::CountingCert> {
238 crate::pigeonhole::counting_certificate(&self.to_expr()?)
239 }
240
241 /// The **full Hall refutation** — the matching invariant in its complete (subset) form. Catches a
242 /// bipartite cover whose totals balance but where some subset of items competes for too few slots,
243 /// returning the violating subset. Strictly stronger than `counting_refutation`.
244 pub fn hall_refutation(&self) -> Option<crate::matching::HallWitness> {
245 crate::pigeonhole::hall_refutation(&self.to_expr()?)
246 }
247
248 /// `Pnp.lean`'s `HasUniqueHole`: exactly one corner is uncovered (search-critical SAT).
249 pub fn has_unique_hole(&self) -> bool {
250 self.solution_count() == 1
251 }
252
253 /// `Pnp.lean`'s `HasAtLeastHoles k`: at least `k` corners remain uncovered (search-easy SAT).
254 pub fn has_at_least_holes(&self, k: u64) -> bool {
255 self.solution_count() >= k
256 }
257
258 /// `Pnp.lean`'s `BlockerFamily.SeparatedBy`: no blocker crosses the coordinate cut `cut` — each
259 /// blocker's support lies entirely inside it or entirely outside. The hypercube version of a
260 /// decomposition separator.
261 pub fn separated_by(&self, cut: u64) -> bool {
262 self.blockers
263 .iter()
264 .all(|b| (b.care & cut) == b.care || (b.care & cut) == 0)
265 }
266
267 /// `Pnp.lean`'s `BlockerFamily.VariableInteraction`: some blocker mentions both `i` and `j` —
268 /// the primal-graph edge of the cover.
269 pub fn variable_interaction(&self, i: usize, j: usize) -> bool {
270 i != j
271 && self
272 .blockers
273 .iter()
274 .any(|b| b.care & (1u64 << i) != 0 && b.care & (1u64 << j) != 0)
275 }
276
277 /// Recover the CNF this cover is the geometry of, as a `ProofExpr` over atoms `x{var}` — the
278 /// door back into the certified prover. `None` when a blocker is the empty clause (an immediate
279 /// contradiction with no propositional form) or the cover has no blockers.
280 pub fn to_expr(&self) -> Option<crate::ProofExpr> {
281 use crate::ProofExpr;
282 let lit = |v: usize, positive: bool| {
283 let a = ProofExpr::Atom(format!("x{v}"));
284 if positive {
285 a
286 } else {
287 ProofExpr::Not(Box::new(a))
288 }
289 };
290 let mut clauses = Vec::with_capacity(self.blockers.len());
291 for b in &self.blockers {
292 let lits = b.clause_literals();
293 if lits.is_empty() {
294 return None;
295 }
296 let mut it = lits.into_iter();
297 let (v0, p0) = it.next().unwrap();
298 clauses.push(it.fold(lit(v0, p0), |acc, (v, p)| {
299 ProofExpr::Or(Box::new(acc), Box::new(lit(v, p)))
300 }));
301 }
302 let mut it = clauses.into_iter();
303 let first = it.next()?;
304 Some(it.fold(first, |acc, c| ProofExpr::And(Box::new(acc), Box::new(c))))
305 }
306
307 /// Decide cover-totality through the **certified prover**, not brute force: route the cover's CNF
308 /// into [`crate::sat::prove_unsat`], which returns a RUP/PR-checked `Refuted` when the cover is
309 /// total (fail-closed — never a false `Refuted`) or a witnessing model when a corner escapes.
310 /// This is what makes the geometry *provable*: pigeonhole covers certify via the counting shadow
311 /// in polynomial time, where resolution would blow up.
312 pub fn prove_total_certified(&self) -> crate::sat::UnsatOutcome {
313 match self.to_expr() {
314 Some(e) => crate::sat::prove_unsat(&e),
315 None => crate::sat::UnsatOutcome::Unsupported,
316 }
317 }
318
319 /// **Reference one rule, get the rules it nets us.** All blockers that resolve with blocker `i`,
320 /// each paired with its pivot and the resolvent it produces — the neighbors of rule `i` in the
321 /// resolution graph, and the new rules they beget.
322 pub fn neighbors(&self, i: usize) -> Vec<(usize, usize, Subcube)> {
323 (0..self.blockers.len())
324 .filter(|&j| j != i)
325 .filter_map(|j| {
326 self.blockers[i]
327 .resolve(&self.blockers[j])
328 .map(|(pivot, r)| (j, pivot, r))
329 })
330 .collect()
331 }
332
333 /// Recover the clauses this cover is the geometry of, as packed [`Lit`]s — the door into the
334 /// automorphism detector and the certified prover's `Lit`-level core.
335 pub fn clauses(&self) -> Vec<Vec<Lit>> {
336 self.blockers
337 .iter()
338 .map(|b| {
339 b.clause_literals()
340 .into_iter()
341 .map(|(v, p)| Lit::new(v as u32, p))
342 .collect()
343 })
344 .collect()
345 }
346
347 /// **Symmetry-break the rules, not the corners.** Partition the blocker indices into orbits under
348 /// the automorphism group generated by `generators`. Each generator must map the blocker *set*
349 /// into itself (it is verified by the image landing back among the blockers); if one ever maps a
350 /// blocker off the set it is not a rule-automorphism and we return `None`, fail-closed.
351 ///
352 /// This is the cheap, powerful move the corner-orbit walk is not: there are only *polynomially*
353 /// many blockers (one per clause), so quotienting the rule set costs `O(generators · blockers ·
354 /// n)` — no `2ⁿ` anywhere. The number of orbits is the count of *essentially distinct rules*: a
355 /// complexity signature of the family computed without ever touching the exponential cube.
356 /// (Assumes distinct blockers, as ordinary CNF families have.)
357 pub fn blocker_orbits(&self, generators: &[CubeSym]) -> Option<Vec<Vec<usize>>> {
358 let mut index: HashMap<Subcube, usize> = HashMap::new();
359 for (i, b) in self.blockers.iter().enumerate() {
360 index.entry(*b).or_insert(i);
361 }
362 let m = self.blockers.len();
363 let mut seen = vec![false; m];
364 let mut orbits = Vec::new();
365 for start in 0..m {
366 if seen[start] {
367 continue;
368 }
369 let mut orbit = Vec::new();
370 let mut stack = vec![start];
371 seen[start] = true;
372 while let Some(i) = stack.pop() {
373 orbit.push(i);
374 for g in generators {
375 let image = g.map_subcube(&self.blockers[i]);
376 let &j = index.get(&image)?; // off the blocker set ⟹ not a rule-automorphism
377 if !seen[j] {
378 seen[j] = true;
379 stack.push(j);
380 }
381 }
382 }
383 orbit.sort_unstable();
384 orbits.push(orbit);
385 }
386 Some(orbits)
387 }
388
389 /// **Discover** this cover's own symmetries and read off its rule-orbit signature — the fully
390 /// self-driving complexity classifier. The detector ([`crate::symmetry_detect::find_generators`])
391 /// returns a generating set of automorphisms as [`Perm`]s, and we quotient the rules by them with
392 /// [`clause_orbits`] (clause-level, so it scales past the geometric cube's 63-variable ceiling).
393 /// A maximally symmetric family (pigeonhole) collapses to a handful of orbits at every scale; a
394 /// random instance, with a trivial automorphism group, collapses to nothing — every rule its own.
395 pub fn discovered_rule_symmetry(&self) -> RuleSymmetry {
396 let clauses = self.clauses();
397 let generators = crate::symmetry_detect::find_generators(self.n, &clauses);
398 let rule_orbits = clause_orbits(&clauses, &generators).len();
399 RuleSymmetry {
400 n: self.n,
401 blockers: clauses.len(),
402 generators: generators.len(),
403 rule_orbits,
404 }
405 }
406}
407
408/// The rule-symmetry signature of a cover: how the polynomially-many blockers collapse under the
409/// family's automorphism group. `rule_orbits` is the count of essentially-distinct rules — a measure
410/// of structural complexity read off *without* enumerating the `2ⁿ` corners. A small, scale-invariant
411/// `rule_orbits` is the geometric fingerprint of a family that admits a short symmetry-broken proof.
412#[derive(Clone, Copy, Debug, PartialEq, Eq)]
413pub struct RuleSymmetry {
414 pub n: usize,
415 pub blockers: usize,
416 pub generators: usize,
417 pub rule_orbits: usize,
418}
419
420/// **Symmetry-break the rules at the clause level** — the lift-and-shift-left form that scales to any
421/// number of variables. Partition the clause indices (the blockers) into orbits under a generating
422/// set of automorphisms, applying each [`Perm`] to clause literals directly via the canonical
423/// `clause_key`. A blocker *is* a clause, so this is the same
424/// rule-quotient as [`Cover::blocker_orbits`] — but with no `2ⁿ` corner geometry and no 63-variable
425/// ceiling, so it runs at scales where the cube is astronomically large. The orbit count is the
426/// number of essentially-distinct rules. (Generators that move a clause off the set are simply not
427/// followed — only genuine rule-automorphisms close orbits.)
428pub fn clause_orbits(clauses: &[Vec<Lit>], generators: &[Perm]) -> Vec<Vec<usize>> {
429 let index: HashMap<Vec<u32>, usize> = clauses
430 .iter()
431 .enumerate()
432 .map(|(i, c)| (crate::symmetry_detect::clause_key(c), i))
433 .collect();
434 let m = clauses.len();
435 let mut seen = vec![false; m];
436 let mut orbits = Vec::new();
437 for start in 0..m {
438 if seen[start] {
439 continue;
440 }
441 let mut orbit = Vec::new();
442 let mut stack = vec![start];
443 seen[start] = true;
444 while let Some(i) = stack.pop() {
445 orbit.push(i);
446 for g in generators {
447 let key = crate::symmetry_detect::clause_key(&g.apply_clause(&clauses[i]));
448 if let Some(&j) = index.get(&key) {
449 if !seen[j] {
450 seen[j] = true;
451 stack.push(j);
452 }
453 }
454 }
455 }
456 orbit.sort_unstable();
457 orbits.push(orbit);
458 }
459 orbits
460}
461
462/// The pigeonhole grid symmetry group `Sₙ × Sₙ₋₁` as scalable [`Perm`]s — adjacent pigeon (row) and
463/// hole (column) transpositions over the `n*(n-1)` grid variables. No `u64` cap.
464pub fn php_perm_symmetries(n: usize) -> Vec<Perm> {
465 let holes = n.saturating_sub(1);
466 let num_vars = n * holes;
467 let var = |p: usize, h: usize| p * holes + h;
468 let mut gens = Vec::new();
469 for p in 0..n.saturating_sub(1) {
470 let mut images: Vec<Lit> = (0..num_vars as u32).map(Lit::pos).collect();
471 for h in 0..holes {
472 images.swap(var(p, h), var(p + 1, h));
473 }
474 gens.push(Perm::from_images(images));
475 }
476 for h in 0..holes.saturating_sub(1) {
477 let mut images: Vec<Lit> = (0..num_vars as u32).map(Lit::pos).collect();
478 for p in 0..n {
479 images.swap(var(p, h), var(p, h + 1));
480 }
481 gens.push(Perm::from_images(images));
482 }
483 gens
484}
485
486/// The rule-symmetry signature of pigeonhole at scale `n`, computed at the clause level with the full
487/// grid group `Sₙ × Sₙ₋₁`. The blocker set grows superlinearly and the cube has `2^{n(n-1)}` corners,
488/// yet the rules always collapse to exactly **two** orbits — the complexity limit symmetry exposes,
489/// computable at any `n` because it never touches the cube.
490pub fn pigeonhole_rule_symmetry(n: usize) -> RuleSymmetry {
491 let (cnf, _) = crate::families::php(n);
492 let generators = php_perm_symmetries(n);
493 let rule_orbits = clause_orbits(&cnf.clauses, &generators).len();
494 RuleSymmetry {
495 n,
496 blockers: cnf.clauses.len(),
497 generators: generators.len(),
498 rule_orbits,
499 }
500}
501
502/// An **abstract, scale-invariant refutation**: the family's rules symmetry-broken to their orbit
503/// *types*, plus the abstract invariant those types violate, plus the constant-size witness. For
504/// pigeonhole this is two rule-types (every pigeon takes a hole; no two share one) and the counting
505/// fact pigeons > holes — identical at every scale. This is the lift-and-shift-left: the proof's true
506/// size is `O(1)` in the rule-types, reached by *symmetry breaking the rules to their types*, never by
507/// enumerating resolvents (the concrete and even the symmetric resolution closure both explode).
508#[derive(Clone, Debug, PartialEq, Eq)]
509pub struct AbstractRefutation {
510 pub rule_types: usize,
511 pub invariant: &'static str,
512 pub witness: crate::pigeonhole::CountingCert,
513}
514
515/// Symmetry-break pigeonhole to its abstract certificate. The rules collapse (via [`clause_orbits`]) to
516/// exactly **two** types regardless of `n`; the abstract invariant on those types is Hall's condition,
517/// witnessed by the `O(1)` counting certificate pigeons > holes. The whole certificate is constant in
518/// size and identical in shape at every scale — the auto-collapse of pigeonhole, lifted to the type
519/// level where it actually scales. `None` only in the degenerate hole-free case.
520pub fn pigeonhole_abstract_refutation(n: usize) -> Option<AbstractRefutation> {
521 let (cnf, _) = crate::families::php(n);
522 let rule_types = clause_orbits(&cnf.clauses, &php_perm_symmetries(n)).len();
523 let witness =
524 crate::pigeonhole::certify_pigeonhole_unsat(n as u128, n.saturating_sub(1) as u128)?;
525 Some(AbstractRefutation {
526 rule_types,
527 invariant: "Hall/matching: pigeons > holes",
528 witness,
529 })
530}
531
532/// Apply a **flip-renaming** `x_v → ¬x_v` for every `v` with `flips[v]` — a phase-flip symmetry of the
533/// cube. It permutes models bijectively (negate the flipped coordinates), so it preserves satisfiability.
534pub fn apply_renaming(clauses: &[Vec<Lit>], flips: &[bool]) -> Vec<Vec<Lit>> {
535 clauses
536 .iter()
537 .map(|c| {
538 c.iter()
539 .map(|l| {
540 if flips[l.var() as usize] {
541 l.negated()
542 } else {
543 *l
544 }
545 })
546 .collect()
547 })
548 .collect()
549}
550
551/// **Recognize a new symmetry: renamable-Horn.** Is there a flip-renaming under which every clause has
552/// at most one positive literal (Horn)? Horn-SAT is polynomial (unit propagation finds the least model),
553/// so a renamable-Horn formula is in a poly class our field cuts cannot see. Crucially, *finding the
554/// renaming is itself a 2-SAT*: a clause is Horn-after-flip iff no two of its literals are both positive,
555/// and "literal `l` is positive after flip" is the single `f`-literal `(l.var, l.is_positive)`. Returns
556/// the flip-set, or `None` if no renaming makes it Horn.
557pub fn renaming_to_horn(num_vars: usize, clauses: &[Vec<Lit>]) -> Option<Vec<bool>> {
558 use crate::twosat::{self, Lit as TLit, TwoSatOutcome};
559 let flit = |l: &Lit| {
560 if l.is_positive() {
561 TLit::pos(l.var() as usize)
562 } else {
563 TLit::neg(l.var() as usize)
564 }
565 };
566 let mut two_sat: Vec<(TLit, TLit)> = Vec::new();
567 for c in clauses {
568 for i in 0..c.len() {
569 for j in (i + 1)..c.len() {
570 two_sat.push((flit(&c[i]), flit(&c[j]))); // ¬(both positive after flip)
571 }
572 }
573 }
574 match twosat::solve(&two_sat, num_vars) {
575 TwoSatOutcome::Sat(flips) => Some(flips),
576 TwoSatOutcome::Unsat(_) => None,
577 }
578}
579
580/// The order of a formula's **automorphism group** — `1` means *rigid* (only the identity preserves it),
581/// the maximally asymmetric extreme. Discovers the generators and closes them under composition.
582pub fn automorphism_group_size(num_vars: usize, clauses: &[Vec<Lit>]) -> usize {
583 let generators = crate::symmetry_detect::find_generators(num_vars, clauses);
584 let key = |p: &Perm| -> Vec<(u32, bool)> {
585 (0..num_vars)
586 .map(|v| {
587 let l = p.apply(Lit::pos(v as u32));
588 (l.var(), l.is_positive())
589 })
590 .collect()
591 };
592 let id = Perm::identity(num_vars);
593 let mut seen: BTreeSet<Vec<(u32, bool)>> = [key(&id)].into_iter().collect();
594 let mut group = vec![id];
595 let mut i = 0;
596 while i < group.len() {
597 let g = group[i].clone();
598 i += 1;
599 for s in &generators {
600 let h = s.compose(&g);
601 if seen.insert(key(&h)) {
602 group.push(h);
603 }
604 }
605 if group.len() > 5_000_000 {
606 break;
607 }
608 }
609 group.len()
610}
611
612/// **Information theory — the bits of symmetry.** `log₂|Aut|` is the symmetry-entropy: the number of
613/// bits the automorphism group compresses out of the formula's description (knowing one orbit
614/// representative plus the group recovers the rest). High for symmetric structure, exactly `0` for a
615/// rigid one — and that zero is the maximal-information, incompressible extreme.
616pub fn symmetry_entropy_bits(num_vars: usize, clauses: &[Vec<Lit>]) -> f64 {
617 (automorphism_group_size(num_vars, clauses) as f64).log2()
618}
619
620/// **Find the randomness.** Strip every structural lever — a certified cut decides it (so there was no
621/// irreducible randomness), carve (unit/pure/subsumption) and bounded variable elimination peel structure
622/// away — and return what survives: the irreducible core. `None` means the instance was fully structured
623/// and got decided. `Some(core)` is the kernel where carving can do no more; check it with [`diagnose`] —
624/// if it also has no cut and ~zero symmetry-bits, *that* is the randomness, isolated.
625pub fn find_random_core(
626 num_vars: usize,
627 clauses: &[Vec<Lit>],
628 max_steps: usize,
629) -> Option<Vec<Vec<Lit>>> {
630 let mut current = clauses.to_vec();
631 for _ in 0..max_steps {
632 let cut = clauses_to_expr(¤t).is_some_and(|e| {
633 crate::pigeonhole::decide_pigeonhole_unsat(&e)
634 || crate::xorsat::refute_via_parity(&e)
635 || crate::pseudo_boolean::refute_clausal(&e)
636 });
637 if cut {
638 return None; // structured — decided by a cut, no randomness to isolate
639 }
640 match carve(num_vars, ¤t) {
641 CarveOutcome::Sat | CarveOutcome::Unsat => return None,
642 CarveOutcome::Core { clauses: core, .. } if core.len() < current.len() => {
643 current = core;
644 }
645 CarveOutcome::Core { clauses: core, .. } => {
646 let eliminated = bounded_variable_elimination(num_vars, &core);
647 if eliminated.len() < core.len() {
648 current = eliminated;
649 } else {
650 return Some(core); // nothing reduces it further — the irreducible core
651 }
652 }
653 }
654 }
655 Some(current)
656}
657
658/// Where `auto_advance` ended: a decided verdict, or the structureless residue (the irreducible core no
659/// structural lever could touch — where you'd branch).
660#[derive(Clone, Debug, PartialEq, Eq)]
661pub enum AdvanceStatus {
662 Decided(bool),
663 StructurelessResidue { core: usize },
664}
665
666/// One step of the self-driving reduction: the lever applied, and the structure remaining after it.
667#[derive(Clone, Debug, PartialEq)]
668pub struct AdvanceStep {
669 pub lever: &'static str,
670 pub clauses: usize,
671 pub symmetry_bits: f64,
672}
673
674/// **Auto-diagnose, auto-break, auto-advance — to the fixpoint.** Repeatedly diagnose the instance and
675/// apply the most decisive lever it offers: a certified cut decides it outright; otherwise carve (unit /
676/// pure-literal / subsumption) and bounded variable elimination peel it down; the loop advances until a
677/// verdict drops out or no structural lever reduces it further — the structureless residue, where the
678/// only remaining move is to branch. The returned trace shows the structure draining away step by step.
679pub fn auto_advance(
680 num_vars: usize,
681 clauses: &[Vec<Lit>],
682 max_steps: usize,
683) -> (AdvanceStatus, Vec<AdvanceStep>) {
684 let mut current = clauses.to_vec();
685 let mut trace = Vec::new();
686 for _ in 0..max_steps {
687 let bits = symmetry_entropy_bits(num_vars, ¤t);
688 // A certified cut decides it.
689 let cut = clauses_to_expr(¤t).is_some_and(|e| {
690 crate::pigeonhole::decide_pigeonhole_unsat(&e)
691 || crate::xorsat::refute_via_parity(&e)
692 || crate::pseudo_boolean::refute_clausal(&e)
693 });
694 if cut {
695 trace.push(AdvanceStep {
696 lever: "certified cut → UNSAT",
697 clauses: current.len(),
698 symmetry_bits: bits,
699 });
700 return (AdvanceStatus::Decided(false), trace);
701 }
702 // Carve.
703 match carve(num_vars, ¤t) {
704 CarveOutcome::Sat => {
705 trace.push(AdvanceStep {
706 lever: "carve → SAT",
707 clauses: 0,
708 symmetry_bits: bits,
709 });
710 return (AdvanceStatus::Decided(true), trace);
711 }
712 CarveOutcome::Unsat => {
713 trace.push(AdvanceStep {
714 lever: "carve → UNSAT",
715 clauses: 0,
716 symmetry_bits: bits,
717 });
718 return (AdvanceStatus::Decided(false), trace);
719 }
720 CarveOutcome::Core { clauses: core, .. } if core.len() < current.len() => {
721 trace.push(AdvanceStep {
722 lever: "carve (unit/pure/subsume)",
723 clauses: core.len(),
724 symmetry_bits: bits,
725 });
726 current = core;
727 continue;
728 }
729 CarveOutcome::Core { clauses: core, .. } => {
730 // No carve reduction — try projecting out a dimension.
731 let eliminated = bounded_variable_elimination(num_vars, &core);
732 if eliminated.len() < core.len() {
733 trace.push(AdvanceStep {
734 lever: "variable elimination (project a dimension)",
735 clauses: eliminated.len(),
736 symmetry_bits: bits,
737 });
738 current = eliminated;
739 continue;
740 }
741 // Nothing reduces it — the structureless residue.
742 trace.push(AdvanceStep {
743 lever: "irreducible core — no structure left (branch)",
744 clauses: core.len(),
745 symmetry_bits: bits,
746 });
747 return (
748 AdvanceStatus::StructurelessResidue { core: core.len() },
749 trace,
750 );
751 }
752 }
753 }
754 (
755 AdvanceStatus::StructurelessResidue {
756 core: current.len(),
757 },
758 trace,
759 )
760}
761
762/// A complete auto-diagnosis of an instance: every structure-detector run at once, so you can read off
763/// the full menu of applicable symmetry-breaks and cuts — *what you can still do to it.*
764#[derive(Clone, Debug, PartialEq)]
765pub struct Diagnosis {
766 pub clauses: usize,
767 pub symmetry_bits: f64,
768 pub rule_quotient: usize,
769 pub cut: Option<Shadow>,
770 pub antipodal: bool,
771 pub renamable_horn: bool,
772 pub components: usize,
773 pub autark_section: bool,
774 pub core_clauses: usize,
775}
776
777/// Run every lever's detector and report what applies. The automated "what can we still do" — one call,
778/// the whole portfolio probed.
779pub fn diagnose(num_vars: usize, clauses: &[Vec<Lit>]) -> Diagnosis {
780 let generators = crate::symmetry_detect::find_generators(num_vars, clauses);
781 let rule_quotient = clause_orbits(clauses, &generators).len();
782 let symmetry_bits = symmetry_entropy_bits(num_vars, clauses);
783 let cut = clauses_to_expr(clauses).and_then(|e| {
784 if crate::pigeonhole::decide_pigeonhole_unsat(&e) {
785 Some(Shadow::Counting)
786 } else if crate::xorsat::refute_via_parity(&e) {
787 Some(Shadow::Parity)
788 } else if crate::pseudo_boolean::refute_clausal(&e) {
789 Some(Shadow::CuttingPlanes)
790 } else {
791 None
792 }
793 });
794 let (_, assigned) = pure_literal_reduce(num_vars, clauses);
795 let core_clauses = match carve(num_vars, clauses) {
796 CarveOutcome::Core { clauses: c, .. } => c.len(),
797 _ => 0,
798 };
799 Diagnosis {
800 clauses: clauses.len(),
801 symmetry_bits,
802 rule_quotient,
803 cut,
804 antipodal: is_antipodally_symmetric(clauses),
805 renamable_horn: renaming_to_horn(num_vars, clauses).is_some(),
806 components: components(num_vars, clauses).len(),
807 autark_section: !assigned.is_empty(),
808 core_clauses,
809 }
810}
811
812/// From a [`Diagnosis`], the list of symmetry-breaks and cuts that apply — the menu of moves, in order
813/// of decisiveness. Empty global structure ⟹ the honest fallback: backdoor + branch on the residue.
814pub fn applicable_levers(d: &Diagnosis) -> Vec<&'static str> {
815 let mut levers = Vec::new();
816 if let Some(s) = d.cut {
817 levers.push(match s {
818 Shadow::Counting => "counting/Hall cut (one-punch)",
819 Shadow::Parity => "GF(2) parity cut (one-punch)",
820 Shadow::CuttingPlanes => "cutting-planes cut (one-punch)",
821 });
822 }
823 if d.symmetry_bits > 0.0 {
824 levers.push("symmetry breaking (lex-leader prune)");
825 }
826 if d.antipodal {
827 levers.push("antipodal / center-inversion (recursive)");
828 }
829 if d.renamable_horn {
830 levers.push("renamable-Horn (poly via 2-SAT renaming)");
831 }
832 if d.components > 1 {
833 levers.push("component decomposition");
834 }
835 if d.autark_section || d.core_clauses < d.clauses {
836 levers.push("autarky / carving (unit, pure-literal, subsumption)");
837 }
838 if levers.is_empty() {
839 levers.push("no global structure — backdoor + branch the residue (the honest wall)");
840 }
841 levers
842}
843
844/// The structural profile of an instance — what every lever reveals about *where its difficulty lives*.
845/// `quotient` is the number of rule orbit-types under its discovered symmetry (how far the cube
846/// collapses); `cut` is the certified shadow that decides it, if any; `core_clauses` is what survives
847/// carving + bounded variable elimination (the irreducible residue). Together they place the instance
848/// on the spectrum from "all symmetry, O(1) quotient, instantly cut" to "no symmetry, full quotient,
849/// nothing reduces — the genuinely interesting core."
850#[derive(Clone, Debug, PartialEq, Eq)]
851pub struct StructuralProfile {
852 pub clauses: usize,
853 pub quotient: usize,
854 pub cut: Option<Shadow>,
855 pub core_clauses: usize,
856}
857
858/// Profile an instance: collapse its rules to orbit-types, probe which cut decides it, and carve it to
859/// its irreducible core. The reading that emerges — quotient size tracks cut-decidability tracks core
860/// reducibility — is the single axis underneath every lever: *difficulty is quotient size.*
861pub fn structural_profile(num_vars: usize, clauses: &[Vec<Lit>]) -> StructuralProfile {
862 let generators = crate::symmetry_detect::find_generators(num_vars, clauses);
863 let quotient = clause_orbits(clauses, &generators).len();
864 let cut = clauses_to_expr(clauses).and_then(|e| {
865 if crate::pigeonhole::decide_pigeonhole_unsat(&e) {
866 Some(Shadow::Counting)
867 } else if crate::xorsat::refute_via_parity(&e) {
868 Some(Shadow::Parity)
869 } else if crate::pseudo_boolean::refute_clausal(&e) {
870 Some(Shadow::CuttingPlanes)
871 } else {
872 None
873 }
874 });
875 let core_clauses = match carve(num_vars, clauses) {
876 CarveOutcome::Sat | CarveOutcome::Unsat => 0,
877 CarveOutcome::Core { clauses: c, .. } => bounded_variable_elimination(num_vars, &c).len(),
878 };
879 StructuralProfile {
880 clauses: clauses.len(),
881 quotient,
882 cut,
883 core_clauses,
884 }
885}
886
887/// Which certified shadow refutes a cover — the abstract class of its hardness.
888#[derive(Clone, Copy, Debug, PartialEq, Eq)]
889pub enum Shadow {
890 /// Counting / matching (pigeonhole, Hall) — resolution-hard, polynomial here.
891 Counting,
892 /// Parity / Gaussian over GF(2) (Tseitin, XOR) — resolution-hard, polynomial here.
893 Parity,
894 /// Cutting planes / cardinality (Farkas hyperplane) — resolution-hard, polynomial here.
895 CuttingPlanes,
896}
897
898/// Push a model through an automorphism: if `σ` preserves the clause set and `m` satisfies it, so does
899/// `σ(m)`. Variable `v`'s value lands on `σ(+v)`'s variable, negated when `σ(+v)` is the negative literal
900/// — chosen so `m ⊨ C ⟹ σ(m) ⊨ σ(C)`.
901pub fn apply_perm_to_model(perm: &Perm, model: &[bool]) -> Vec<bool> {
902 let mut out = model.to_vec();
903 for v in 0..model.len() {
904 let image = perm.apply(Lit::pos(v as u32));
905 out[image.var() as usize] = if image.is_positive() {
906 model[v]
907 } else {
908 !model[v]
909 };
910 }
911 out
912}
913
914/// **Symmetry generates solutions.** From one model, the entire orbit under a generating set of
915/// automorphisms — every member a model too, produced with no search. The generative dual of resolution
916/// (which begets *rules* from symmetry); here symmetry begets *solutions*.
917pub fn model_orbit(model: &[bool], generators: &[Perm]) -> Vec<Vec<bool>> {
918 let mut seen = BTreeSet::new();
919 seen.insert(model.to_vec());
920 let mut stack = vec![model.to_vec()];
921 while let Some(m) = stack.pop() {
922 for g in generators {
923 let image = apply_perm_to_model(g, &m);
924 if seen.insert(image.clone()) {
925 stack.push(image);
926 }
927 }
928 }
929 seen.into_iter().collect()
930}
931
932/// **Symmetry-break the witness.** The canonical (lexicographically least) model in a witness's orbit
933/// under the automorphisms — the symmetry-broken representative. All witnesses in one orbit reduce to the
934/// same canonical witness, so the *essential* content of the solution set is one canonical witness per
935/// orbit; the symmetry regenerates the rest via [`model_orbit`].
936pub fn canonical_model(model: &[bool], generators: &[Perm]) -> Vec<bool> {
937 model_orbit(model, generators).into_iter().min().unwrap()
938}
939
940/// The full symmetry group: every distinct `Perm` reachable by composing the generators (closure under
941/// composition). Small-group only — the orbit-stabilizer accounting below needs the *whole* group, not a
942/// generating set. Includes the identity.
943pub fn perm_group_closure(generators: &[Perm], num_vars: usize) -> Vec<Perm> {
944 let mut seen = std::collections::HashSet::new();
945 let id = Perm::identity(num_vars);
946 let mut frontier = vec![id.clone()];
947 seen.insert(id);
948 while let Some(g) = frontier.pop() {
949 for h in generators {
950 let gh = h.compose(&g);
951 if seen.insert(gh.clone()) {
952 frontier.push(gh);
953 }
954 }
955 }
956 seen.into_iter().collect()
957}
958
959/// **The stabilizer of a witness** — the subgroup of symmetries that fix it (`σ·m = m`). These are the
960/// transformations under which the witness sees *itself*; they are exactly the redundancy in its
961/// perspective of the others.
962pub fn stabilizer(model: &[bool], group: &[Perm]) -> Vec<Perm> {
963 group
964 .iter()
965 .filter(|g| apply_perm_to_model(g, model) == model)
966 .cloned()
967 .collect()
968}
969
970/// **Symmetry-break across the witness's perspective of the other witnesses.** From witness `m`, every
971/// other witness in its orbit is reached by *some* symmetry — but many symmetries land on the same one
972/// (they differ by a stabilizer element of `m`). The symmetry-broken perspective quotients that
973/// redundancy out: exactly **one** representative transformation per distinct witness `m` can see — a
974/// transversal of the coset space `G / Stab(m)`. The returned `(witness, σ)` pairs satisfy `σ·m =
975/// witness`, and their count is `|G| / |Stab(m)| = |orbit(m)|` (orbit–stabilizer). The first entry is
976/// `(m, identity)`: the witness's view of itself.
977pub fn witness_perspective(
978 model: &[bool],
979 generators: &[Perm],
980 num_vars: usize,
981) -> Vec<(Vec<bool>, Perm)> {
982 let group = perm_group_closure(generators, num_vars);
983 let mut seen = BTreeSet::new();
984 let mut out = Vec::new();
985 let mut by_dest: Vec<(Vec<bool>, Perm)> = Vec::new();
986 for g in &group {
987 let dest = apply_perm_to_model(g, model);
988 if seen.insert(dest.clone()) {
989 by_dest.push((dest, g.clone()));
990 }
991 }
992 by_dest.sort_by(|a, b| a.0.cmp(&b.0));
993 let here = by_dest.iter().position(|(d, _)| d == model).unwrap();
994 out.push((model.to_vec(), Perm::identity(num_vars)));
995 for (i, pair) in by_dest.into_iter().enumerate() {
996 if i != here {
997 out.push(pair);
998 }
999 }
1000 out
1001}
1002
1003/// **Burnside orbit count — the number of essentially-distinct witnesses.** By Burnside's lemma the
1004/// number of orbits of a group action equals the *average* number of fixed points:
1005/// `#orbits = (1/|G|) · Σ_{g∈G} |Fix(g)|`, where `Fix(g) = { m : g·m = m }`. Applied to the solution
1006/// set (closed under the automorphisms, since every `g` is an automorphism), this counts the witnesses
1007/// **up to symmetry** — the essential solutions — as a fixed-point average, never enumerating an orbit.
1008/// The sum is exactly divisible by `|G|` (the lemma guarantees it); `group` must be the *whole* group
1009/// (use [`perm_group_closure`]).
1010pub fn burnside_orbit_count(models: &[Vec<bool>], group: &[Perm]) -> usize {
1011 let total_fixed: usize = group
1012 .iter()
1013 .map(|g| {
1014 models
1015 .iter()
1016 .filter(|m| apply_perm_to_model(g, m.as_slice()) == **m)
1017 .count()
1018 })
1019 .sum();
1020 total_fixed / group.len()
1021}
1022
1023/// **Where an UNSAT instance sits in the proof-complexity landscape**, as our certified cuts see it.
1024/// This is a *ladder of proof systems* (Cook–Reckhow): each rung crushes families the cheaper ones are
1025/// blind to. `Counting` and `Parity` are **incomparable narrow detectors** — pigeonhole needs counting
1026/// and is invisible to GF(2); Tseitin needs GF(2) and is invisible to counting — while
1027/// `Nullstellensatz{min_degree}` is the *universal algebraic height* over GF(2), complete at degree `n`.
1028/// The honest face of the wall: an instance whose narrow cuts are silent and whose minimum NS degree is
1029/// large sits at the top of this ladder, and the cost *at* that height is exponential. We can *locate* an
1030/// instance on the ladder; we cannot prove the top rung is unavoidable for a family — that lower bound is
1031/// exactly P vs NP, and it stays open.
1032#[derive(Clone, Copy, Debug, PartialEq, Eq)]
1033pub enum ProofRung {
1034 /// Closed by unit propagation / carving alone — no real refutation needed.
1035 Trivial,
1036 /// A counting / Hall (pigeonhole) cut crushes it. Resolution-exponential families like PHP live here;
1037 /// incomparable to `Parity`.
1038 Counting,
1039 /// A GF(2) parity (Gaussian-elimination) cut crushes it. Tseitin / XOR families live here;
1040 /// incomparable to `Counting`.
1041 Parity,
1042 /// A certified mod-`p` Gaussian cut crushes it — `Parity` carried to the odd prime `p`: the CNF is a
1043 /// recognized one-hot encoding of a `GF(p)` linear system whose refutation re-checks. One rung per
1044 /// characteristic, each incomparable to the others and to `Counting`/`Parity` (the prime
1045 /// incomparability of `polycalc_gfp`). Reported only by the extended cascade
1046 /// ([`weakest_crushing_rung_with_char`]); the legacy cascade predates the characteristic axis.
1047 ModCount { p: u64 },
1048 /// No narrow cut fires; refuted only by Nullstellensatz / Polynomial Calculus over GF(2) at this
1049 /// minimum degree — the universal algebraic height. The rigid residue lives here.
1050 Nullstellensatz { min_degree: usize },
1051 /// No cut and no NS refutation within the degree budget — the wall as our detectors perceive it.
1052 BeyondBudget,
1053}
1054
1055/// Locate an instance on the [`ProofRung`] ladder: the *weakest* certified cut that crushes it, probed
1056/// cheapest-first (carve ≺ counting ≺ parity ≺ Nullstellensatz-by-degree). The narrow rungs (`Counting`,
1057/// `Parity`) are incomparable; probe order only decides the label when more than one happens to fire.
1058///
1059/// **This has no satisfiability oracle.** `BeyondBudget` means *no certified cut fired* — which covers
1060/// **both** a satisfiable instance **and** a hard-UNSAT one beyond the degree budget. Our detectors
1061/// cannot tell those two apart cheaply; that very indistinguishability is the wall, and resolving it for
1062/// a family (proving the budget *must* be exceeded) is P vs NP.
1063pub fn weakest_crushing_rung(num_vars: usize, clauses: &[Vec<Lit>], ns_budget: usize) -> ProofRung {
1064 weakest_crushing_rung_with_char(num_vars, clauses, ns_budget, &[])
1065}
1066
1067/// [`weakest_crushing_rung`] with the **characteristic rungs enabled** — the same cascade, plus, between
1068/// the parity probe and the algebraic ascent, a certified mod-`p` cut per prime in `primes`: when the
1069/// CNF is a recognized one-hot encoding of a `GF(p)` linear system ([`crate::modp::recover_from_cnf`],
1070/// which declines rather than guesses) and the `GF(p)` Gaussian refutation re-checks
1071/// ([`crate::modp::is_refutation`]), the instance lands on [`ProofRung::ModCount`]. This is the ladder
1072/// rung the census's `router_beats_ladder` audit flagged as missing: the structured router's
1073/// `Route::ModP` specialist finally has a certified proof system the ladder can name. With
1074/// `primes = &[]` the cascade is exactly the legacy one.
1075pub fn weakest_crushing_rung_with_char(
1076 num_vars: usize,
1077 clauses: &[Vec<Lit>],
1078 ns_budget: usize,
1079 primes: &[u64],
1080) -> ProofRung {
1081 if let CarveOutcome::Unsat = carve(num_vars, clauses) {
1082 return ProofRung::Trivial;
1083 }
1084 let Some(e) = clauses_to_expr(clauses) else {
1085 return ProofRung::BeyondBudget;
1086 };
1087 if crate::pigeonhole::counting_certificate(&e).is_some()
1088 || crate::pigeonhole::hall_refutation(&e).is_some()
1089 {
1090 return ProofRung::Counting;
1091 }
1092 if crate::xorsat::refute_via_parity(&e) {
1093 return ProofRung::Parity;
1094 }
1095 if !primes.is_empty() {
1096 if let Some(rec) = crate::modp::recover_from_cnf(num_vars, clauses) {
1097 if primes.contains(&rec.modulus) {
1098 if let crate::modp::ModpOutcome::Unsat(combo) =
1099 crate::modp::solve(&rec.equations, rec.num_vars, rec.modulus)
1100 {
1101 if crate::modp::is_refutation(&rec.equations, rec.num_vars, rec.modulus, &combo)
1102 {
1103 return ProofRung::ModCount { p: rec.modulus };
1104 }
1105 }
1106 }
1107 }
1108 }
1109 let cap = ns_budget.min(num_vars);
1110 if let Some(d) =
1111 (1..=cap).find(|&d| crate::polycalc::nullstellensatz_refutes(num_vars, clauses, d))
1112 {
1113 return ProofRung::Nullstellensatz { min_degree: d };
1114 }
1115 ProofRung::BeyondBudget
1116}
1117
1118/// **Symmetry-aware solution counting.** Partition a set of models into orbits under a generating set
1119/// of automorphisms; each orbit is the full `model_orbit` of any of its members. The solution count is
1120/// the sum of the orbit sizes, so a symmetric instance collapses to *one representative per orbit* — far
1121/// fewer than the solutions themselves. (`models` should be closed under the symmetry, e.g. all models.)
1122pub fn partition_into_orbits(models: &[Vec<bool>], generators: &[Perm]) -> Vec<Vec<Vec<bool>>> {
1123 let model_set: BTreeSet<Vec<bool>> = models.iter().cloned().collect();
1124 let mut assigned: BTreeSet<Vec<bool>> = BTreeSet::new();
1125 let mut orbits = Vec::new();
1126 for m in models {
1127 if assigned.contains(m) {
1128 continue;
1129 }
1130 let orbit: Vec<Vec<bool>> = model_orbit(m, generators)
1131 .into_iter()
1132 .filter(|x| model_set.contains(x))
1133 .collect();
1134 for x in &orbit {
1135 assigned.insert(x.clone());
1136 }
1137 orbits.push(orbit);
1138 }
1139 orbits
1140}
1141
1142/// **Autocarve — recursive carving that lets the rules fall out.** Carve the formula to its core,
1143/// decompose into independent components, and for each: if a certified cut recognizes it, the rule
1144/// *falls out* and the component closes; otherwise branch one variable and **carve again** on each
1145/// branch. Every decision cascades fresh unit propagations and pure literals, exposing structure the
1146/// previous level hid — so a buried, masked, or nested invariant surfaces on its own at the depth it
1147/// becomes visible. UNSAT iff any component is, SAT iff all are; `None` past the budget.
1148/// What an autocarve run did: how many recursion nodes it visited, how many times a certified cut
1149/// *fired* (a "punch"), and how deep the carving recursed.
1150#[derive(Clone, Copy, Debug, Default, PartialEq, Eq)]
1151pub struct CarveStats {
1152 pub nodes: usize,
1153 pub punches: usize,
1154 pub max_depth: usize,
1155}
1156
1157pub fn autocarve(num_vars: usize, clauses: &[Vec<Lit>], budget: usize) -> Option<bool> {
1158 autocarve_measured(num_vars, clauses, budget).0
1159}
1160
1161/// Like [`autocarve`], but also returns the [`CarveStats`] — node count, punch count, recursion depth.
1162pub fn autocarve_measured(
1163 num_vars: usize,
1164 clauses: &[Vec<Lit>],
1165 budget: usize,
1166) -> (Option<bool>, CarveStats) {
1167 let mut stats = CarveStats::default();
1168 let verdict = autocarve_rec(num_vars, clauses, budget, 0, &mut stats);
1169 (verdict, stats)
1170}
1171
1172fn autocarve_rec(
1173 num_vars: usize,
1174 clauses: &[Vec<Lit>],
1175 budget: usize,
1176 depth: usize,
1177 stats: &mut CarveStats,
1178) -> Option<bool> {
1179 stats.nodes += 1;
1180 stats.max_depth = stats.max_depth.max(depth);
1181 if stats.nodes > budget {
1182 return None;
1183 }
1184 let core = match carve(num_vars, clauses) {
1185 CarveOutcome::Sat => return Some(true),
1186 CarveOutcome::Unsat => return Some(false),
1187 CarveOutcome::Core { clauses, .. } => clauses,
1188 };
1189 for component in components(num_vars, &core) {
1190 // The rule falls out: a certified cut recognizes the carved component — a punch. The full-set
1191 // counting bound (`items > slots`) is the *symmetric* special case — O(1) after extraction, no
1192 // matching — so try it first; only fall back to the general Hall matching when it doesn't fire.
1193 let cut = clauses_to_expr(&component).is_some_and(|e| {
1194 crate::pigeonhole::counting_certificate(&e).is_some()
1195 || crate::pigeonhole::decide_pigeonhole_unsat(&e)
1196 || crate::xorsat::refute_via_parity(&e)
1197 || crate::pseudo_boolean::refute_clausal(&e)
1198 });
1199 if cut {
1200 stats.punches += 1;
1201 return Some(false); // a UNSAT component refutes the whole formula
1202 }
1203 // Otherwise branch and carve again — the structure surfaces one decision deeper.
1204 let pivot = component[0][0].var();
1205 let mut component_sat = false;
1206 for value in [false, true] {
1207 let mut branch = component.clone();
1208 branch.push(vec![Lit::new(pivot, value)]);
1209 match autocarve_rec(num_vars, &branch, budget, depth + 1, stats) {
1210 Some(true) => {
1211 component_sat = true;
1212 break;
1213 }
1214 Some(false) => {}
1215 None => return None,
1216 }
1217 }
1218 if !component_sat {
1219 return Some(false); // both branches UNSAT ⟹ this component, and the whole formula, is UNSAT
1220 }
1221 }
1222 Some(true)
1223}
1224
1225/// **The unified crush.** Compose every lever into one decision procedure: carve the autark sections
1226/// (pure literals), split into independent components, and decide each by the cut-enabled
1227/// symmetry-aware search — a component refuted by a certified cut at the root closes in one node, the
1228/// rest fall to bounded branch-and-cut. The formula is UNSAT iff any component is, SAT iff all are.
1229/// Returns `None` only when a component blows past the budget — the genuinely hard residue, honestly
1230/// surfaced rather than hidden.
1231pub fn crush(num_vars: usize, clauses: &[Vec<Lit>], budget: usize) -> Option<bool> {
1232 let (core, _) = pure_literal_reduce(num_vars, clauses);
1233 if core.is_empty() {
1234 return Some(true); // every section carved away — satisfiable
1235 }
1236 for component in components(num_vars, &core) {
1237 match search_cost(num_vars, &component, true, budget) {
1238 SearchCost::Decided { sat: false, .. } => return Some(false), // a UNSAT component refutes all
1239 SearchCost::Decided { sat: true, .. } => {} // satisfiable, keep going
1240 SearchCost::Exceeded { .. } => return None, // the hard residue
1241 }
1242 }
1243 Some(true) // every component satisfiable
1244}
1245
1246fn resolve_on_var(cp: &[Lit], cn: &[Lit], v: usize) -> Option<Vec<Lit>> {
1247 let mut lits: Vec<Lit> = Vec::new();
1248 for &l in cp.iter().chain(cn.iter()) {
1249 if l.var() as usize != v && !lits.contains(&l) {
1250 lits.push(l);
1251 }
1252 }
1253 if lits.iter().any(|l| lits.contains(&l.negated())) {
1254 return None; // tautological resolvent — discard
1255 }
1256 Some(lits)
1257}
1258
1259/// **Carve out a dimension.** Eliminate variable `v` by resolution (Davis–Putnam): drop every clause
1260/// mentioning `v`, and add the non-tautological resolvents of each `v`-clause against each `¬v`-clause.
1261/// Geometrically this *projects the cube's `v`-axis away* — the formula over `n` dimensions becomes an
1262/// equisatisfiable one over `n-1`. Sound: a model of the projection lifts to a model of the original.
1263pub fn eliminate_variable(v: usize, clauses: &[Vec<Lit>]) -> Vec<Vec<Lit>> {
1264 let (pv, nv) = (Lit::new(v as u32, true), Lit::new(v as u32, false));
1265 let mut result: Vec<Vec<Lit>> = clauses
1266 .iter()
1267 .filter(|c| !c.contains(&pv) && !c.contains(&nv))
1268 .cloned()
1269 .collect();
1270 let pos: Vec<&Vec<Lit>> = clauses.iter().filter(|c| c.contains(&pv)).collect();
1271 let neg: Vec<&Vec<Lit>> = clauses.iter().filter(|c| c.contains(&nv)).collect();
1272 for cp in &pos {
1273 for cn in &neg {
1274 if let Some(resolvent) = resolve_on_var(cp, cn, v) {
1275 result.push(resolvent);
1276 }
1277 }
1278 }
1279 result
1280}
1281
1282/// **Bounded variable elimination** — carve away every dimension whose projection doesn't grow the
1283/// formula (resolvents ≤ clauses removed). Iterated to a fixpoint, it peels the cube down dimension by
1284/// dimension wherever it's free to do so; the variables that *would* explode (pigeonhole's, by Haken)
1285/// are left for the cuts. Satisfiability-preserving.
1286pub fn bounded_variable_elimination(num_vars: usize, clauses: &[Vec<Lit>]) -> Vec<Vec<Lit>> {
1287 let mut current = clauses.to_vec();
1288 loop {
1289 let mut eliminated = false;
1290 for v in 0..num_vars {
1291 let pos = current
1292 .iter()
1293 .filter(|c| c.contains(&Lit::new(v as u32, true)))
1294 .count();
1295 let neg = current
1296 .iter()
1297 .filter(|c| c.contains(&Lit::new(v as u32, false)))
1298 .count();
1299 if pos == 0 || neg == 0 {
1300 continue;
1301 }
1302 let candidate = eliminate_variable(v, ¤t);
1303 if candidate.len() <= current.len() {
1304 current = candidate;
1305 eliminated = true;
1306 }
1307 }
1308 if !eliminated {
1309 break;
1310 }
1311 }
1312 current
1313}
1314
1315/// What carving the hypercube reduced a formula to.
1316#[derive(Clone, Debug, PartialEq, Eq)]
1317pub enum CarveOutcome {
1318 /// Carved to nothing — satisfiable.
1319 Sat,
1320 /// Carved to an empty clause — unsatisfiable.
1321 Unsat,
1322 /// Carved to an irreducible core, plus the literals forced along the way.
1323 Core {
1324 clauses: Vec<Vec<Lit>>,
1325 forced: Vec<Lit>,
1326 },
1327}
1328
1329fn find_pure_literal(num_vars: usize, clauses: &[Vec<Lit>]) -> Option<Lit> {
1330 let mut pos = vec![false; num_vars];
1331 let mut neg = vec![false; num_vars];
1332 for c in clauses {
1333 for l in c {
1334 if l.is_positive() {
1335 pos[l.var() as usize] = true;
1336 } else {
1337 neg[l.var() as usize] = true;
1338 }
1339 }
1340 }
1341 (0..num_vars).find_map(|v| match (pos[v], neg[v]) {
1342 (true, false) => Some(Lit::new(v as u32, true)),
1343 (false, true) => Some(Lit::new(v as u32, false)),
1344 _ => None,
1345 })
1346}
1347
1348fn subsume_once(clauses: &mut Vec<Vec<Lit>>) -> bool {
1349 for i in 0..clauses.len() {
1350 for j in 0..clauses.len() {
1351 if i != j
1352 && clauses[i].len() < clauses[j].len()
1353 && clauses[i].iter().all(|l| clauses[j].contains(l))
1354 {
1355 clauses.remove(j);
1356 return true;
1357 }
1358 }
1359 }
1360 false
1361}
1362
1363/// **Carve away the hypercube.** Peel the formula down by the three classic simplifications, iterated to
1364/// a fixpoint: *unit propagation* (a unit clause carves the cube in half by forcing a variable),
1365/// *pure-literal* assignment (carves an autark section), and *subsumption* (drops a blocker contained in
1366/// a stronger one). All three preserve satisfiability, so the result is either a verdict or the
1367/// irreducible core that genuine hardness leaves behind. Pigeonhole carves to itself.
1368pub fn carve(num_vars: usize, clauses: &[Vec<Lit>]) -> CarveOutcome {
1369 let mut current: Vec<Vec<Lit>> = clauses.to_vec();
1370 let mut forced: Vec<Lit> = Vec::new();
1371 loop {
1372 if current.iter().any(|c| c.is_empty()) {
1373 return CarveOutcome::Unsat;
1374 }
1375 if current.is_empty() {
1376 return CarveOutcome::Sat;
1377 }
1378 let mut changed = false;
1379 if let Some(unit) = current.iter().find(|c| c.len() == 1).map(|c| c[0]) {
1380 forced.push(unit);
1381 let neg = unit.negated();
1382 current.retain(|c| !c.contains(&unit));
1383 for c in &mut current {
1384 c.retain(|&l| l != neg);
1385 }
1386 changed = true;
1387 } else if let Some(pure) = find_pure_literal(num_vars, ¤t) {
1388 forced.push(pure);
1389 current.retain(|c| !c.contains(&pure));
1390 changed = true;
1391 } else if subsume_once(&mut current) {
1392 changed = true;
1393 }
1394 if !changed {
1395 return CarveOutcome::Core {
1396 clauses: current,
1397 forced,
1398 };
1399 }
1400 }
1401}
1402
1403/// **Cut out the autark sections.** A *pure literal* (a variable appearing in only one polarity) is the
1404/// simplest autarky: assigning it satisfies every clause it touches, so that whole section of the cube is
1405/// removed without affecting satisfiability. Iterate to a fixpoint and what remains is the hard core —
1406/// the part with no free section to cut. Returns `(core clauses, assigned pure literals)`. Sound: pure-
1407/// literal elimination preserves satisfiability (Davis–Putnam).
1408pub fn pure_literal_reduce(num_vars: usize, clauses: &[Vec<Lit>]) -> (Vec<Vec<Lit>>, Vec<Lit>) {
1409 let mut current: Vec<Vec<Lit>> = clauses.to_vec();
1410 let mut assigned = Vec::new();
1411 loop {
1412 let mut pos = vec![false; num_vars];
1413 let mut neg = vec![false; num_vars];
1414 for c in ¤t {
1415 for l in c {
1416 if l.is_positive() {
1417 pos[l.var() as usize] = true;
1418 } else {
1419 neg[l.var() as usize] = true;
1420 }
1421 }
1422 }
1423 let pure = (0..num_vars).find_map(|v| match (pos[v], neg[v]) {
1424 (true, false) => Some(Lit::new(v as u32, true)),
1425 (false, true) => Some(Lit::new(v as u32, false)),
1426 _ => None,
1427 });
1428 let Some(l) = pure else { break };
1429 assigned.push(l);
1430 current.retain(|c| !c.iter().any(|&x| x == l));
1431 }
1432 (current, assigned)
1433}
1434
1435/// Partition a formula into its **independent components** — maximal clause groups sharing no variable
1436/// (the connected components of the variable-interaction graph). The formula is the conjunction of its
1437/// components, so it is UNSAT iff *any* component is, and each can be attacked on its own. A structured
1438/// UNSAT component buried in a big mixed formula — invisible to the monolithic cut — is laid bare here.
1439pub fn components(num_vars: usize, clauses: &[Vec<Lit>]) -> Vec<Vec<Vec<Lit>>> {
1440 fn find(parent: &mut [usize], mut x: usize) -> usize {
1441 while parent[x] != x {
1442 parent[x] = parent[parent[x]];
1443 x = parent[x];
1444 }
1445 x
1446 }
1447 let mut parent: Vec<usize> = (0..num_vars.max(1)).collect();
1448 for clause in clauses {
1449 let vars: Vec<usize> = clause.iter().map(|l| l.var() as usize).collect();
1450 for pair in vars.windows(2) {
1451 let (a, b) = (find(&mut parent, pair[0]), find(&mut parent, pair[1]));
1452 parent[a] = b;
1453 }
1454 }
1455 let mut groups: HashMap<usize, Vec<Vec<Lit>>> = HashMap::new();
1456 for clause in clauses {
1457 let root = clause
1458 .first()
1459 .map(|l| find(&mut parent, l.var() as usize))
1460 .unwrap_or(0);
1461 groups.entry(root).or_default().push(clause.clone());
1462 }
1463 groups.into_values().collect()
1464}
1465
1466/// Decompose into independent components and crush: return `true` (UNSAT) the moment any component is
1467/// refuted by a certified cut, never having examined the rest. Isolating a structured UNSAT component
1468/// unlocks a cut the monolithic formula hides.
1469pub fn decompose_and_crush(num_vars: usize, clauses: &[Vec<Lit>]) -> bool {
1470 components(num_vars, clauses).iter().any(|comp| {
1471 clauses_to_expr(comp).is_some_and(|e| {
1472 crate::pigeonhole::decide_pigeonhole_unsat(&e)
1473 || crate::xorsat::refute_via_parity(&e)
1474 || crate::pseudo_boolean::refute_clausal(&e)
1475 })
1476 })
1477}
1478
1479/// Is the cover invariant under the **antipodal map** — global negation `x → ¬x`, the center-inversion
1480/// of the cube? True iff flipping every literal of every clause maps the clause set onto itself. This is
1481/// a symmetry axis *distinct* from coordinate permutation: it is the involution whose unique fixed point
1482/// is the ½-center ([`CubeSym::map_fractional`] with all flips and no permutation fixes `½ⁿ`). When it
1483/// holds, satisfying assignments come in antipodal pairs `{a, ¬a}`, so one variable's value is free WLOG.
1484pub fn is_antipodally_symmetric(clauses: &[Vec<Lit>]) -> bool {
1485 let key = |c: &[Lit]| -> Vec<u32> {
1486 let mut k: Vec<u32> = c
1487 .iter()
1488 .map(|l| l.var() * 2 + u32::from(!l.is_positive()))
1489 .collect();
1490 k.sort_unstable();
1491 k.dedup();
1492 k
1493 };
1494 let original: BTreeSet<Vec<u32>> = clauses.iter().map(|c| key(c)).collect();
1495 let flipped: BTreeSet<Vec<u32>> = clauses
1496 .iter()
1497 .map(|c| key(&c.iter().map(|l| l.negated()).collect::<Vec<_>>()))
1498 .collect();
1499 original == flipped
1500}
1501
1502/// What a laddered branch-and-cut search did: how many subcubes (nodes) it visited, how deep it
1503/// laddered, and how many subtrees a certified cut closed outright.
1504#[derive(Clone, Copy, Debug, PartialEq, Eq)]
1505pub struct LadderStats {
1506 pub nodes: usize,
1507 pub max_depth: usize,
1508 pub cut_closures: usize,
1509 pub pruned: usize,
1510}
1511
1512/// **Ladder up the hypercube: crush what we can, brute-force the rest.** Branch-and-cut over `{0,1}ⁿ`,
1513/// one variable at a time — exactly DPLL with our certified cuts as the theory:
1514/// 1. **base** — a residual empty clause means this subcube is fully covered (UNSAT branch); no
1515/// residual clauses means a corner escapes here (SAT).
1516/// 2. **unit propagation** — a residual unit clause forces its variable (free dimension reduction).
1517/// 3. **cut** — try the certified shadows (counting / parity / cutting-planes) on the residual; if one
1518/// fires, the whole subcube is crushed without descending — the learned invariant doing its work.
1519/// 4. **branch** — otherwise split on a residual variable and ladder down.
1520///
1521/// Structured families (pigeonhole, Tseitin, clique) are crushed by a cut at or near the root in a
1522/// handful of nodes *at any `n`*, because the cut is scale-free; the genuinely unstructured residual is
1523/// brute-forced by the branching. Works on raw clauses, so it ladders past the cube's 63-variable
1524/// geometric ceiling.
1525pub fn decide_laddered(num_vars: usize, clauses: &[Vec<Lit>]) -> (bool, LadderStats) {
1526 let mut stats = LadderStats {
1527 nodes: 0,
1528 max_depth: 0,
1529 cut_closures: 0,
1530 pruned: 0,
1531 };
1532 let sat = ladder(clauses, vec![None; num_vars], 0, &mut stats);
1533 (sat, stats)
1534}
1535
1536/// **Symmetry-break the search itself.** The same branch-and-cut ladder, but it branches variables in
1537/// index order and *prunes* a node whenever a root automorphism maps its decided prefix to a
1538/// lexicographically smaller decided assignment — classic lex-leader symmetry breaking during search.
1539/// Sound by construction: every orbit of assignments keeps exactly one lex-leader, and only strict
1540/// non-leaders are pruned, so the verdict never changes; symmetric subtrees are simply skipped. The
1541/// automorphisms are discovered once at the root.
1542pub fn decide_laddered_sym(
1543 num_vars: usize,
1544 clauses: &[Vec<Lit>],
1545 use_cut: bool,
1546) -> (bool, LadderStats) {
1547 let generators = crate::symmetry_detect::find_generators(num_vars, clauses);
1548 let mut stats = LadderStats {
1549 nodes: 0,
1550 max_depth: 0,
1551 cut_closures: 0,
1552 pruned: 0,
1553 };
1554 let sat = ladder_sym(
1555 clauses,
1556 vec![None; num_vars],
1557 0,
1558 &generators,
1559 use_cut,
1560 &mut stats,
1561 );
1562 (sat, stats)
1563}
1564
1565/// The baseline the symmetry-pruned search is measured against: the *same* branch engine with no cut
1566/// and no generators (so `violates_lex_leader` never fires). Isolates the effect of symmetry pruning.
1567pub fn decide_laddered_nocut(num_vars: usize, clauses: &[Vec<Lit>]) -> (bool, LadderStats) {
1568 let mut stats = LadderStats {
1569 nodes: 0,
1570 max_depth: 0,
1571 cut_closures: 0,
1572 pruned: 0,
1573 };
1574 let sat = ladder_sym(clauses, vec![None; num_vars], 0, &[], false, &mut stats);
1575 (sat, stats)
1576}
1577
1578/// The measured cost of a branch search: either it decided within the node budget, or the search blew
1579/// past it (the exponential explosion, captured rather than hung).
1580#[derive(Clone, Copy, Debug, PartialEq, Eq)]
1581pub enum SearchCost {
1582 Decided { sat: bool, nodes: usize },
1583 Exceeded { budget: usize },
1584}
1585
1586/// Run the branch engine purely to **measure** its size, with `use_cut` selecting whether the certified
1587/// cuts fire, and a hard `budget` on visited nodes so a resolution-class explosion is recorded as
1588/// `Exceeded` instead of running forever. With the cut off this is raw DPLL (resolution-strength); with
1589/// it on, the certified cut closes whole subtrees. The apples-to-apples gap between the two is the
1590/// campaign's thesis, quantified.
1591pub fn search_cost(
1592 num_vars: usize,
1593 clauses: &[Vec<Lit>],
1594 use_cut: bool,
1595 budget: usize,
1596) -> SearchCost {
1597 let mut nodes = 0usize;
1598 match cost_rec(clauses, vec![None; num_vars], use_cut, budget, &mut nodes) {
1599 Some(sat) => SearchCost::Decided { sat, nodes },
1600 None => SearchCost::Exceeded { budget },
1601 }
1602}
1603
1604/// **Recursive antipodal symmetry breaking.** Branch search that, at *every* node, re-detects whether
1605/// the residual is antipodally symmetric ([`is_antipodally_symmetric`]); when it is, it fixes the pivot
1606/// to `false` WLOG and prunes the `true` branch — soundly, since the residual's models come in antipodal
1607/// pairs. A disjoint union of self-complementary blocks keeps regaining the symmetry as each block's
1608/// first variable is fixed, so the break fires *recursively*, collapsing one factor of 2 per block.
1609pub fn search_cost_antipodal(num_vars: usize, clauses: &[Vec<Lit>], budget: usize) -> SearchCost {
1610 let mut nodes = 0usize;
1611 match antipodal_rec(clauses, vec![None; num_vars], budget, &mut nodes) {
1612 Some(sat) => SearchCost::Decided { sat, nodes },
1613 None => SearchCost::Exceeded { budget },
1614 }
1615}
1616
1617fn antipodal_rec(
1618 clauses: &[Vec<Lit>],
1619 assignment: Vec<Option<bool>>,
1620 budget: usize,
1621 nodes: &mut usize,
1622) -> Option<bool> {
1623 *nodes += 1;
1624 if *nodes > budget {
1625 return None;
1626 }
1627 let residual = restrict(clauses, &assignment);
1628 if residual.iter().any(|c| c.is_empty()) {
1629 return Some(false);
1630 }
1631 if residual.is_empty() {
1632 return Some(true);
1633 }
1634 let pivot = residual[0][0].var() as usize;
1635 // When the residual is antipodally symmetric, the `true` branch mirrors the `false` one — prune it.
1636 let values: &[bool] = if is_antipodally_symmetric(&residual) {
1637 &[false]
1638 } else {
1639 &[false, true]
1640 };
1641 for &value in values {
1642 let mut next = assignment.clone();
1643 next[pivot] = Some(value);
1644 match antipodal_rec(clauses, next, budget, nodes) {
1645 Some(true) => return Some(true),
1646 Some(false) => {}
1647 None => return None,
1648 }
1649 }
1650 Some(false)
1651}
1652
1653fn cost_rec(
1654 clauses: &[Vec<Lit>],
1655 assignment: Vec<Option<bool>>,
1656 use_cut: bool,
1657 budget: usize,
1658 nodes: &mut usize,
1659) -> Option<bool> {
1660 *nodes += 1;
1661 if *nodes > budget {
1662 return None;
1663 }
1664 let residual = restrict(clauses, &assignment);
1665 if residual.iter().any(|c| c.is_empty()) {
1666 return Some(false);
1667 }
1668 if residual.is_empty() {
1669 return Some(true);
1670 }
1671 if use_cut {
1672 if let Some(e) = clauses_to_expr(&residual) {
1673 if crate::pigeonhole::decide_pigeonhole_unsat(&e)
1674 || crate::xorsat::refute_via_parity(&e)
1675 || crate::pseudo_boolean::refute_clausal(&e)
1676 {
1677 return Some(false);
1678 }
1679 }
1680 }
1681 let Some(pivot) = assignment.iter().position(|a| a.is_none()) else {
1682 return Some(true);
1683 };
1684 for value in [false, true] {
1685 let mut next = assignment.clone();
1686 next[pivot] = Some(value);
1687 match cost_rec(clauses, next, use_cut, budget, nodes) {
1688 Some(true) => return Some(true),
1689 Some(false) => {}
1690 None => return None,
1691 }
1692 }
1693 Some(false)
1694}
1695
1696fn ladder_sym(
1697 clauses: &[Vec<Lit>],
1698 assignment: Vec<Option<bool>>,
1699 depth: usize,
1700 generators: &[Perm],
1701 use_cut: bool,
1702 stats: &mut LadderStats,
1703) -> bool {
1704 stats.nodes += 1;
1705 stats.max_depth = stats.max_depth.max(depth);
1706 let residual = restrict(clauses, &assignment);
1707 if residual.iter().any(|c| c.is_empty()) {
1708 return false;
1709 }
1710 if residual.is_empty() {
1711 return true;
1712 }
1713 if use_cut {
1714 if let Some(e) = clauses_to_expr(&residual) {
1715 if crate::pigeonhole::decide_pigeonhole_unsat(&e)
1716 || crate::xorsat::refute_via_parity(&e)
1717 || crate::pseudo_boolean::refute_clausal(&e)
1718 {
1719 stats.cut_closures += 1;
1720 return false;
1721 }
1722 }
1723 }
1724 // Branch the lowest-index undecided variable (index order is what makes lex-leader sound).
1725 let Some(pivot) = assignment.iter().position(|a| a.is_none()) else {
1726 return true;
1727 };
1728 for value in [false, true] {
1729 let mut next = assignment.clone();
1730 next[pivot] = Some(value);
1731 if violates_lex_leader(&next, generators) {
1732 stats.pruned += 1;
1733 continue; // a symmetric, lex-smaller assignment is explored on an earlier branch
1734 }
1735 if ladder_sym(clauses, next, depth + 1, generators, use_cut, stats) {
1736 return true;
1737 }
1738 }
1739 false
1740}
1741
1742/// Does some generator map the decided prefix of `a` to a lexicographically *smaller* decided
1743/// assignment over the same decided set? If so, `a` is not the lex-leader of its orbit and may be
1744/// pruned. Sound: an automorphism decreasing `a` proves the leader is strictly below `a`. (Checking
1745/// generators, not the whole group, only prunes *less* — never unsoundly.)
1746fn violates_lex_leader(a: &[Option<bool>], generators: &[Perm]) -> bool {
1747 let n = a.len();
1748 for sigma in generators {
1749 let mut b = vec![None; n];
1750 for v in 0..n {
1751 if let Some(val) = a[v] {
1752 let image = sigma.apply(Lit::pos(v as u32));
1753 b[image.var() as usize] = Some(if image.is_positive() { val } else { !val });
1754 }
1755 }
1756 // Only compare when σ keeps the decided set fixed (a clean restricted comparison).
1757 if (0..n).any(|v| a[v].is_some() != b[v].is_some()) {
1758 continue;
1759 }
1760 // Lexicographic compare b against a; prune iff b < a (false < true at the first difference).
1761 for v in 0..n {
1762 if let (Some(av), Some(bv)) = (a[v], b[v]) {
1763 if av != bv {
1764 if !bv {
1765 return true;
1766 }
1767 break;
1768 }
1769 }
1770 }
1771 }
1772 false
1773}
1774
1775fn ladder(
1776 clauses: &[Vec<Lit>],
1777 assignment: Vec<Option<bool>>,
1778 depth: usize,
1779 stats: &mut LadderStats,
1780) -> bool {
1781 stats.nodes += 1;
1782 stats.max_depth = stats.max_depth.max(depth);
1783 let residual = restrict(clauses, &assignment);
1784 if residual.iter().any(|c| c.is_empty()) {
1785 return false; // an empty clause: this subcube is fully covered — UNSAT branch
1786 }
1787 if residual.is_empty() {
1788 return true; // nothing left to cover: a corner escapes — SAT
1789 }
1790 // Unit propagation: a forced literal reduces the free dimension with no branching.
1791 if let Some(unit) = residual.iter().find(|c| c.len() == 1) {
1792 let l = unit[0];
1793 let mut next = assignment.clone();
1794 next[l.var() as usize] = Some(l.is_positive());
1795 return ladder(clauses, next, depth + 1, stats);
1796 }
1797 // Cut: a certified shadow crushes the whole subcube if it recognizes the residual.
1798 if let Some(e) = clauses_to_expr(&residual) {
1799 if crate::pigeonhole::decide_pigeonhole_unsat(&e)
1800 || crate::xorsat::refute_via_parity(&e)
1801 || crate::pseudo_boolean::refute_clausal(&e)
1802 {
1803 stats.cut_closures += 1;
1804 return false;
1805 }
1806 }
1807 // Branch: split on a residual variable and ladder down (residual clauses are width ≥ 2 here).
1808 let pivot = residual[0][0].var() as usize;
1809 for value in [false, true] {
1810 let mut next = assignment.clone();
1811 next[pivot] = Some(value);
1812 if ladder(clauses, next, depth + 1, stats) {
1813 return true;
1814 }
1815 }
1816 false
1817}
1818
1819/// The verdict of auto-cutting a cover: which certified cut showed it total (no corner escapes), or
1820/// that a corner escapes (satisfiable), or that it is not a cover the prover decides.
1821#[derive(Clone, Debug, PartialEq, Eq)]
1822pub enum CoverVerdict {
1823 /// Total cover — UNSAT, every corner blocked. `cut` names the structured hyperplane family that
1824 /// certified it in polynomial time (counting / parity / cutting-planes), or `None` when the general
1825 /// certified prover (symmetry-broken CDCL → RUP) closed it.
1826 Total { cut: Option<Shadow> },
1827 /// A corner escapes the cover — satisfiable.
1828 Escapes,
1829 /// Not a propositional cover the prover handles.
1830 Unknown,
1831}
1832
1833impl Cover {
1834 /// **Auto-cut and crush.** Try each certified cut in turn — the counting hyperplane (Hall), the
1835 /// affine GF(2) cut (Gaussian), the cardinality cutting plane (Farkas) — and fall back to the
1836 /// general certified prover if no structured cut fits. One call, every family: it reports which
1837 /// hyperplane family closed the cover, or that a corner escapes. This is the whole campaign behind
1838 /// a single door — and it is exactly `sat::prove_unsat`'s cascade, surfaced with the cut it used.
1839 pub fn auto_certify(&self) -> CoverVerdict {
1840 let Some(e) = self.to_expr() else {
1841 return CoverVerdict::Unknown;
1842 };
1843 if crate::pigeonhole::decide_pigeonhole_unsat(&e) {
1844 return CoverVerdict::Total {
1845 cut: Some(Shadow::Counting),
1846 };
1847 }
1848 if crate::xorsat::refute_via_parity(&e) {
1849 return CoverVerdict::Total {
1850 cut: Some(Shadow::Parity),
1851 };
1852 }
1853 if crate::pseudo_boolean::refute_clausal(&e) {
1854 return CoverVerdict::Total {
1855 cut: Some(Shadow::CuttingPlanes),
1856 };
1857 }
1858 match crate::sat::prove_unsat(&e) {
1859 crate::sat::UnsatOutcome::Refuted => CoverVerdict::Total { cut: None },
1860 crate::sat::UnsatOutcome::Sat(_) => CoverVerdict::Escapes,
1861 crate::sat::UnsatOutcome::Unsupported => CoverVerdict::Unknown,
1862 }
1863 }
1864}
1865
1866/// The abstract signature of a family: its rules symmetry-broken to their orbit *types*, and which
1867/// certified shadow (if any) refutes it. This is the auto-collapse spread across families — the same
1868/// machinery that found pigeonhole's two-type counting abstraction, applied blind to any cover.
1869#[derive(Clone, Debug, PartialEq, Eq)]
1870pub struct FamilySignature {
1871 pub num_vars: usize,
1872 pub clauses: usize,
1873 pub rule_types: usize,
1874 pub shadow: Option<Shadow>,
1875}
1876
1877/// Symmetry-break any cover to its abstract signature: discover its automorphisms, quotient the rules
1878/// to orbit-types ([`clause_orbits`]), and probe the certified shadows in turn — counting, then parity,
1879/// then cutting-planes. `shadow = None` means no shadow recognizes it (it falls through to the general
1880/// certified CDCL core). A maximally symmetric family collapses to a few rule-types decided by one
1881/// shadow; an unstructured one spreads across many types with no shadow — but still has a backdoor.
1882pub fn abstract_signature(num_vars: usize, clauses: &[Vec<Lit>]) -> FamilySignature {
1883 let generators = crate::symmetry_detect::find_generators(num_vars, clauses);
1884 let rule_types = clause_orbits(clauses, &generators).len();
1885 let shadow = clauses_to_expr(clauses).and_then(|e| {
1886 if crate::pigeonhole::decide_pigeonhole_unsat(&e) {
1887 Some(Shadow::Counting)
1888 } else if crate::xorsat::refute_via_parity(&e) {
1889 Some(Shadow::Parity)
1890 } else if crate::pseudo_boolean::refute_clausal(&e) {
1891 Some(Shadow::CuttingPlanes)
1892 } else {
1893 None
1894 }
1895 });
1896 FamilySignature {
1897 num_vars,
1898 clauses: clauses.len(),
1899 rule_types,
1900 shadow,
1901 }
1902}
1903
1904// ---- There is no such thing as random: backdoors to easy classes -------------------------------
1905//
1906// A "statistically random" instance is, once generated, a fixed deterministic object with definite
1907// structure — it merely lacks an obvious *global* symmetry. Its structure is *local*: a small set of
1908// variables (a **backdoor**) whose every fixing collapses the residual into a polynomially-decidable
1909// class. Hardness without a clean global symmetry is not noise; it is unfound structure. These
1910// primitives find that structure and use it — `2^k` easy branches instead of a `2ⁿ` search — which is
1911// also exactly how symmetry breaking buys *speed*, not just classification.
1912
1913/// The residual CNF after fixing variables: `assignment[v] = Some(b)` fixes `v`, `None` leaves it
1914/// free. Clauses satisfied by a fixed literal are dropped; falsified literals are removed. An empty
1915/// clause in the result means the restriction already falsifies the formula.
1916pub fn restrict(clauses: &[Vec<Lit>], assignment: &[Option<bool>]) -> Vec<Vec<Lit>> {
1917 let mut out = Vec::new();
1918 'clause: for c in clauses {
1919 let mut residual = Vec::new();
1920 for &l in c {
1921 match assignment.get(l.var() as usize).copied().flatten() {
1922 Some(value) => {
1923 if value == l.is_positive() {
1924 continue 'clause; // a fixed literal satisfies the clause — drop it
1925 }
1926 // otherwise the literal is falsified — omit it from the residual
1927 }
1928 None => residual.push(l),
1929 }
1930 }
1931 out.push(residual);
1932 }
1933 out
1934}
1935
1936fn to_twosat_lit(l: Lit) -> crate::twosat::Lit {
1937 if l.is_positive() {
1938 crate::twosat::Lit::pos(l.var() as usize)
1939 } else {
1940 crate::twosat::Lit::neg(l.var() as usize)
1941 }
1942}
1943
1944/// Decide a width-≤2 CNF in polynomial time via the 2-SAT SCC solver. `true` = satisfiable. An empty
1945/// clause forces UNSAT. Panics if handed a clause wider than 2 (not a 2-SAT instance).
1946pub fn decide_2sat(clauses: &[Vec<Lit>], num_vars: usize) -> bool {
1947 let mut pairs = Vec::with_capacity(clauses.len());
1948 for c in clauses {
1949 match c.as_slice() {
1950 [] => return false,
1951 [a] => pairs.push((to_twosat_lit(*a), to_twosat_lit(*a))),
1952 [a, b] => pairs.push((to_twosat_lit(*a), to_twosat_lit(*b))),
1953 _ => panic!("decide_2sat given a width-{} clause", c.len()),
1954 }
1955 }
1956 matches!(
1957 crate::twosat::solve(&pairs, num_vars),
1958 crate::twosat::TwoSatOutcome::Sat(_)
1959 )
1960}
1961
1962/// Greedily find a **backdoor to 2-SAT**: a set of variables `U` such that every clause has at most
1963/// two literals outside `U`. Then under *any* assignment to `U`, each clause is either satisfied or
1964/// shrinks to width ≤ 2, so the residual is 2-SAT — poly-decidable. Built by repeatedly fixing the
1965/// variable that appears in the most still-too-wide clauses (a hitting set of the wide clauses).
1966pub fn greedy_2sat_backdoor(clauses: &[Vec<Lit>], num_vars: usize) -> Vec<usize> {
1967 let mut chosen = vec![false; num_vars];
1968 let mut backdoor = Vec::new();
1969 loop {
1970 let mut freq = vec![0usize; num_vars];
1971 let mut any_wide = false;
1972 for c in clauses {
1973 let free = c.iter().filter(|l| !chosen[l.var() as usize]).count();
1974 if free > 2 {
1975 any_wide = true;
1976 for l in c {
1977 if !chosen[l.var() as usize] {
1978 freq[l.var() as usize] += 1;
1979 }
1980 }
1981 }
1982 }
1983 if !any_wide {
1984 break;
1985 }
1986 let best = (0..num_vars).max_by_key(|&v| freq[v]).unwrap();
1987 chosen[best] = true;
1988 backdoor.push(best);
1989 }
1990 backdoor.sort_unstable();
1991 backdoor
1992}
1993
1994/// Verify `U` is a **strong** backdoor to 2-SAT by enumeration: every one of the `2^{|U|}` assignments
1995/// to `U` yields a residual of width ≤ 2. Bounded to `|U| ≤ 24` (the enumeration guard).
1996pub fn is_strong_backdoor_to_2sat(
1997 clauses: &[Vec<Lit>],
1998 num_vars: usize,
1999 backdoor: &[usize],
2000) -> bool {
2001 let k = backdoor.len();
2002 if k > 24 {
2003 return false;
2004 }
2005 for mask in 0u32..(1u32 << k) {
2006 let mut assignment = vec![None; num_vars];
2007 for (i, &v) in backdoor.iter().enumerate() {
2008 assignment[v] = Some(mask & (1 << i) != 0);
2009 }
2010 if restrict(clauses, &assignment).iter().any(|c| c.len() > 2) {
2011 return false;
2012 }
2013 }
2014 true
2015}
2016
2017/// Decide satisfiability through a 2-SAT backdoor: the instance is satisfiable iff *some* fixing of
2018/// `U` leaves a satisfiable 2-SAT residual. This solves in `2^{|U|}` polynomial branches instead of a
2019/// `2ⁿ` search — the structure (the backdoor) turned an exponential into a small, easy fan-out. `U`
2020/// must be a strong backdoor to 2-SAT (every residual width ≤ 2).
2021pub fn decide_sat_via_2sat_backdoor(
2022 clauses: &[Vec<Lit>],
2023 num_vars: usize,
2024 backdoor: &[usize],
2025) -> bool {
2026 for mask in 0u32..(1u32 << backdoor.len()) {
2027 let mut assignment = vec![None; num_vars];
2028 for (i, &v) in backdoor.iter().enumerate() {
2029 assignment[v] = Some(mask & (1 << i) != 0);
2030 }
2031 let residual = restrict(clauses, &assignment);
2032 if decide_2sat(&residual, num_vars) {
2033 return true;
2034 }
2035 }
2036 false
2037}
2038
2039/// The orbit representative (canonical form) of a blocker under a generating set: the lexicographically
2040/// minimal blocker reachable through the generators. Two blockers are symmetric iff they share a
2041/// canonical form, so canonicalizing is how a symmetry-aware engine dedups derived rules by orbit.
2042pub fn canonical_blocker(b: &Subcube, generators: &[CubeSym]) -> Subcube {
2043 let mut best = *b;
2044 let mut seen = BTreeSet::new();
2045 seen.insert(*b);
2046 let mut stack = vec![*b];
2047 while let Some(x) = stack.pop() {
2048 for g in generators {
2049 let y = g.map_subcube(&x);
2050 if seen.insert(y) {
2051 if y < best {
2052 best = y;
2053 }
2054 stack.push(y);
2055 }
2056 }
2057 }
2058 best
2059}
2060
2061/// The full orbit of a blocker under the group generated by `generators` (BFS over images). For a
2062/// structured family this is *polynomial*-sized even though `|G|` is astronomical, because the
2063/// blocker's stabilizer is huge (a pigeonhole exclusion has orbit `holes·C(pigeons,2)`, not `|G|`).
2064pub fn blocker_orbit(b: &Subcube, generators: &[CubeSym]) -> Vec<Subcube> {
2065 let mut seen = BTreeSet::new();
2066 seen.insert(*b);
2067 let mut stack = vec![*b];
2068 while let Some(x) = stack.pop() {
2069 for g in generators {
2070 let y = g.map_subcube(&x);
2071 if seen.insert(y) {
2072 stack.push(y);
2073 }
2074 }
2075 }
2076 seen.into_iter().collect()
2077}
2078
2079/// Symmetric resolution closure on orbit *representatives*: resolve each representative against every
2080/// image in another representative's orbit. Since resolution commutes with symmetry — `σ(resolve(c,d))
2081/// = resolve(σc,σd)` — this captures every derivable rule up to symmetry without building the raw
2082/// exponential closure. Returns the saturated count of orbit-types and whether the empty clause (a
2083/// refutation) was derived, bounded by `max_rounds` and a `max_reps` size guard.
2084///
2085/// **Measured limit (honest):** this refutes PHP(3) at 12 orbit-types but does **not** scale — at
2086/// PHP(4) the symmetric closure already explodes past tens of thousands of types. Even quotiented by
2087/// symmetry, the *full* resolution closure is the wrong abstraction; the `max_reps` guard makes it fail
2088/// safe rather than run away. The scalable path is [`pigeonhole_abstract_refutation`] — lift to the
2089/// rule-type level and apply the counting invariant, not the closure.
2090pub fn symmetric_resolution_closure(
2091 cover: &Cover,
2092 generators: &[CubeSym],
2093 max_rounds: usize,
2094 max_reps: usize,
2095) -> (usize, bool) {
2096 let empty = Subcube {
2097 n: cover.n,
2098 care: 0,
2099 value: 0,
2100 };
2101 let mut reps: BTreeSet<Subcube> = cover
2102 .blockers
2103 .iter()
2104 .map(|b| canonical_blocker(b, generators))
2105 .collect();
2106 let mut refuted = reps.contains(&empty);
2107 for _ in 0..max_rounds {
2108 if refuted {
2109 break;
2110 }
2111 let current: Vec<Subcube> = reps.iter().copied().collect();
2112 let orbits: Vec<Vec<Subcube>> = current
2113 .iter()
2114 .map(|d| blocker_orbit(d, generators))
2115 .collect();
2116 let mut added = false;
2117 'outer: for c in ¤t {
2118 for orbit in &orbits {
2119 for image in orbit {
2120 if let Some((_, r)) = c.resolve(image) {
2121 let canon = canonical_blocker(&r, generators);
2122 if reps.insert(canon) {
2123 added = true;
2124 if canon == empty {
2125 refuted = true;
2126 break 'outer;
2127 }
2128 if reps.len() > max_reps {
2129 break 'outer;
2130 }
2131 }
2132 }
2133 }
2134 }
2135 }
2136 if !added {
2137 break;
2138 }
2139 }
2140 (reps.len(), refuted)
2141}
2142
2143/// **Symmetric resolution closure — rules beget rules, collapsed by symmetry.** From a cover's
2144/// blockers, repeatedly resolve all pairs (each resolvent a new rule) and record, per round, both the
2145/// raw count of distinct derived rules and the count of their *orbit representatives* under the
2146/// automorphism group. The widening gap between the two is the symmetry collapse of the resolution
2147/// proof: raw resolution explodes, but modulo symmetry only a handful of essentially-distinct rules
2148/// are ever derived — the geometric reason symmetric proof systems refute pigeonhole in polynomial
2149/// size where plain resolution cannot.
2150pub fn symmetric_resolution_growth(
2151 cover: &Cover,
2152 generators: &[CubeSym],
2153 rounds: usize,
2154) -> Vec<(usize, usize)> {
2155 let mut raw: BTreeSet<Subcube> = cover.blockers.iter().copied().collect();
2156 let mut out = Vec::new();
2157 for _ in 0..rounds {
2158 let current: Vec<Subcube> = raw.iter().copied().collect();
2159 for i in 0..current.len() {
2160 for j in (i + 1)..current.len() {
2161 if let Some((_, r)) = current[i].resolve(¤t[j]) {
2162 raw.insert(r);
2163 }
2164 }
2165 }
2166 let orbits: BTreeSet<Subcube> = raw
2167 .iter()
2168 .map(|b| canonical_blocker(b, generators))
2169 .collect();
2170 out.push((raw.len(), orbits.len()));
2171 }
2172 out
2173}
2174
2175/// **Symmetry breaking for speed.** Count the orbits of the `2^{|U|}` backdoor branches (assignments
2176/// to `U`) under the generators that preserve `U` setwise. A symmetry-aware solver inspects one branch
2177/// per orbit instead of all `2^{|U|}` — fewer poly-time solves for the same verdict. Generators that
2178/// move `U` off itself do not act on the branches and are skipped; each kept generator induces a
2179/// permutation-with-flips on the backdoor positions.
2180pub fn backdoor_branch_orbit_count(backdoor: &[usize], generators: &[Perm]) -> u64 {
2181 let k = backdoor.len();
2182 let position: HashMap<usize, usize> =
2183 backdoor.iter().enumerate().map(|(i, &v)| (v, i)).collect();
2184 let mut induced: Vec<(Vec<usize>, u32)> = Vec::new();
2185 for g in generators {
2186 let mut perm = vec![0usize; k];
2187 let mut flip = 0u32;
2188 let mut preserves = true;
2189 for (i, &v) in backdoor.iter().enumerate() {
2190 let image = g.apply(Lit::pos(v as u32));
2191 match position.get(&(image.var() as usize)) {
2192 Some(&j) => {
2193 perm[i] = j;
2194 if !image.is_positive() {
2195 flip |= 1 << j;
2196 }
2197 }
2198 None => {
2199 preserves = false;
2200 break;
2201 }
2202 }
2203 }
2204 if preserves {
2205 induced.push((perm, flip));
2206 }
2207 }
2208 let total = 1u32 << k;
2209 let mut seen = vec![false; total as usize];
2210 let mut orbits = 0u64;
2211 for start in 0..total {
2212 if seen[start as usize] {
2213 continue;
2214 }
2215 orbits += 1;
2216 let mut stack = vec![start];
2217 seen[start as usize] = true;
2218 while let Some(m) = stack.pop() {
2219 for (perm, flip) in &induced {
2220 let mut image = 0u32;
2221 for i in 0..k {
2222 if m & (1 << i) != 0 {
2223 image |= 1 << perm[i];
2224 }
2225 }
2226 image ^= flip;
2227 if !seen[image as usize] {
2228 seen[image as usize] = true;
2229 stack.push(image);
2230 }
2231 }
2232 }
2233 }
2234 orbits
2235}
2236
2237/// Build the CNF `ProofExpr` over atoms `x{var}` from raw clauses — the door into the certified
2238/// prover, scalable (no cube). `None` on an empty clause or empty formula.
2239pub fn clauses_to_expr(clauses: &[Vec<Lit>]) -> Option<crate::ProofExpr> {
2240 use crate::ProofExpr;
2241 let lit = |l: &Lit| {
2242 let a = ProofExpr::Atom(format!("x{}", l.var()));
2243 if l.is_positive() {
2244 a
2245 } else {
2246 ProofExpr::Not(Box::new(a))
2247 }
2248 };
2249 // Combine `nodes` into a BALANCED binary tree (depth O(log n)) rather than a linear left spine, so a
2250 // flat CNF's connective tree is logarithmically deep. Every recursive walker over it (clause
2251 // collectors, clausifiers, evaluators) then recurses O(log n) deep and cannot overflow the stack on
2252 // a several-thousand-clause formula — the pathological structure simply is never built.
2253 fn balanced(
2254 mut nodes: Vec<ProofExpr>,
2255 combine: impl Fn(Box<ProofExpr>, Box<ProofExpr>) -> ProofExpr,
2256 ) -> ProofExpr {
2257 while nodes.len() > 1 {
2258 let mut next = Vec::with_capacity((nodes.len() + 1) / 2);
2259 let mut it = nodes.into_iter();
2260 while let Some(a) = it.next() {
2261 match it.next() {
2262 Some(b) => next.push(combine(Box::new(a), Box::new(b))),
2263 None => next.push(a),
2264 }
2265 }
2266 nodes = next;
2267 }
2268 nodes
2269 .into_iter()
2270 .next()
2271 .expect("balanced() requires a non-empty node list")
2272 }
2273 let mut built = Vec::with_capacity(clauses.len());
2274 for c in clauses {
2275 if c.is_empty() {
2276 return None;
2277 }
2278 let lits: Vec<ProofExpr> = c.iter().map(|l| lit(l)).collect();
2279 built.push(balanced(lits, |a, b| ProofExpr::Or(a, b)));
2280 }
2281 if built.is_empty() {
2282 return None;
2283 }
2284 Some(balanced(built, |a, b| crate::ProofExpr::And(a, b)))
2285}
2286
2287/// A hypercube symmetry: permute coordinates, then optionally flip each one (`Pnp.lean`'s
2288/// `CubeSymmetry`). `perm[j]` is the coordinate that `j`'s value lands on; `flip[j]` negates it.
2289/// These are the automorphisms that move blockers among blockers and corners among corners with the
2290/// **same** action — the bridge that puts rules and solutions in one mathematical world.
2291#[derive(Clone, Debug)]
2292pub struct CubeSym {
2293 pub perm: Vec<usize>,
2294 pub flip: Vec<bool>,
2295}
2296
2297impl CubeSym {
2298 /// The identity symmetry on `n` coordinates.
2299 pub fn identity(n: usize) -> CubeSym {
2300 CubeSym {
2301 perm: (0..n).collect(),
2302 flip: vec![false; n],
2303 }
2304 }
2305
2306 /// Push a corner forward through the symmetry (`mapVertex`): coordinate `j`'s (possibly flipped)
2307 /// value moves to coordinate `perm[j]`.
2308 pub fn map_corner(&self, c: Corner) -> Corner {
2309 let mut out = 0u64;
2310 for j in 0..self.perm.len() {
2311 let mut bit = (c >> j) & 1;
2312 if self.flip[j] {
2313 bit ^= 1;
2314 }
2315 out |= bit << self.perm[j];
2316 }
2317 out
2318 }
2319
2320 /// Push a blocker forward through the symmetry (`mapBlocker`): each fixed coordinate `j` moves
2321 /// to `perm[j]`, its required value flipped when `flip[j]`.
2322 pub fn map_subcube(&self, s: &Subcube) -> Subcube {
2323 let mut care = 0u64;
2324 let mut value = 0u64;
2325 for j in 0..self.perm.len() {
2326 if s.care & (1u64 << j) != 0 {
2327 let pj = self.perm[j];
2328 care |= 1u64 << pj;
2329 let mut bit = (s.value >> j) & 1;
2330 if self.flip[j] {
2331 bit ^= 1;
2332 }
2333 value |= bit << pj;
2334 }
2335 }
2336 Subcube {
2337 n: s.n,
2338 care,
2339 value,
2340 }
2341 }
2342
2343 /// Act on a *fractional* point of the cube `[0,1]ⁿ`: coordinate `j`'s value (flipped to `1−x` when
2344 /// `flip[j]`) lands on coordinate `perm[j]`. The linear extension of `map_corner` to the solid cube.
2345 pub fn map_fractional(&self, point: &[f64]) -> Vec<f64> {
2346 let mut out = vec![0.0; self.perm.len()];
2347 for j in 0..self.perm.len() {
2348 out[self.perm[j]] = if self.flip[j] {
2349 1.0 - point[j]
2350 } else {
2351 point[j]
2352 };
2353 }
2354 out
2355 }
2356
2357 /// Compose two cube symmetries: `(self ∘ other)` applies `other` then `self`.
2358 pub fn compose(&self, other: &CubeSym) -> CubeSym {
2359 let n = self.perm.len();
2360 let mut perm = vec![0usize; n];
2361 let mut flip = vec![false; n];
2362 for j in 0..n {
2363 let mid = other.perm[j];
2364 perm[j] = self.perm[mid];
2365 flip[j] = other.flip[j] ^ self.flip[mid];
2366 }
2367 CubeSym { perm, flip }
2368 }
2369
2370 /// Is this symmetry an **automorphism** of the cover — does it map the blocker *set* onto
2371 /// itself? Re-verified directly (the soundness check), exactly as `swap_is_automorphism` is for
2372 /// the clausal path: a finder that proposes a non-automorphism is caught here, never trusted.
2373 pub fn is_automorphism(&self, cover: &Cover) -> bool {
2374 let original: BTreeSet<Subcube> = cover.blockers.iter().copied().collect();
2375 let mapped: BTreeSet<Subcube> =
2376 cover.blockers.iter().map(|b| self.map_subcube(b)).collect();
2377 original == mapped
2378 }
2379}
2380
2381/// The group generated by `generators` (closure under composition) — for small groups, so the
2382/// combinatorial orbit-counting lemma can sum over every element.
2383fn group_closure(generators: &[CubeSym], n: usize) -> Vec<CubeSym> {
2384 let id = CubeSym::identity(n);
2385 let key = |g: &CubeSym| (g.perm.clone(), g.flip.clone());
2386 let mut seen: BTreeSet<(Vec<usize>, Vec<bool>)> = [key(&id)].into_iter().collect();
2387 let mut group = vec![id];
2388 let mut i = 0;
2389 while i < group.len() {
2390 let g = group[i].clone();
2391 i += 1;
2392 for s in generators {
2393 let h = s.compose(&g);
2394 if seen.insert(key(&h)) {
2395 group.push(h);
2396 }
2397 }
2398 if group.len() > 200_000 {
2399 break;
2400 }
2401 }
2402 group
2403}
2404
2405/// **Combinatorics — Burnside's lemma.** The number of corner orbits equals the *average* number of
2406/// corners fixed by a group element: `(1/|G|) Σ_g |Fix(g)|`. A different invariant for the same count the
2407/// orbit-BFS computes — counting by fixed points instead of by walking orbits. (`n ≤ ~16`.)
2408pub fn burnside_corner_orbits(n: usize, generators: &[CubeSym]) -> u64 {
2409 let group = group_closure(generators, n);
2410 let fixed_total: u128 = group
2411 .iter()
2412 .map(|g| {
2413 (0u64..(1u64 << n))
2414 .filter(|&c| g.map_corner(c) == c)
2415 .count() as u128
2416 })
2417 .sum();
2418 (fixed_total / group.len() as u128) as u64
2419}
2420
2421/// **Analysis — the Walsh–Hadamard (Fourier) spectrum.** Expand the cover's vertex-energy function over
2422/// the cube's characters `χ_S(x) = (-1)^{⟨S,x⟩}`: `f̂(S) = 2⁻ⁿ Σ_x energy(x) χ_S(x)`. Harmonic analysis on
2423/// the hypercube — the coefficients are the analytic invariant. (`n ≤ ~16`.)
2424pub fn walsh_hadamard_energy(cover: &Cover) -> Vec<f64> {
2425 let size = 1usize << cover.n;
2426 let f: Vec<f64> = (0..size as u64)
2427 .map(|x| cover.vertex_energy(x) as f64)
2428 .collect();
2429 (0..size)
2430 .map(|s| {
2431 let acc: f64 = (0..size)
2432 .map(|x| {
2433 if ((s & x) as u64).count_ones() % 2 == 0 {
2434 f[x]
2435 } else {
2436 -f[x]
2437 }
2438 })
2439 .sum();
2440 acc / size as f64
2441 })
2442 .collect()
2443}
2444
2445/// **Geometry — the f-vector.** The number of blockers of each face dimension. A symmetry permutes
2446/// blockers among themselves but preserves each one's dimension, so the f-vector is a geometric invariant
2447/// of the cover (the discrete analog of a polytope's face counts).
2448pub fn face_vector(cover: &Cover) -> std::collections::BTreeMap<usize, usize> {
2449 let mut fv = std::collections::BTreeMap::new();
2450 for b in &cover.blockers {
2451 *fv.entry(b.dimension()).or_insert(0) += 1;
2452 }
2453 fv
2454}
2455
2456/// Orbit partition of the `2ⁿ` corners under a set of generators, each a verified automorphism.
2457/// Returns one representative per orbit (the orbit-collapsed corner set the cover check needs).
2458/// Materializes a `2ⁿ` seen-bitmap, so this is itself bounded by the hypercube size — it *measures*
2459/// the collapse rather than escaping it; the counting/parity shadows are what decide totality
2460/// without the `2ⁿ` walk. Honest by construction.
2461pub fn orbit_representatives(n: usize, generators: &[CubeSym]) -> Vec<Corner> {
2462 let total = 1u64 << n;
2463 let mut seen = vec![false; total as usize];
2464 let mut reps = Vec::new();
2465 for start in 0u64..total {
2466 if seen[start as usize] {
2467 continue;
2468 }
2469 reps.push(start);
2470 let mut stack = vec![start];
2471 seen[start as usize] = true;
2472 while let Some(c) = stack.pop() {
2473 for g in generators {
2474 let d = g.map_corner(c);
2475 if !seen[d as usize] {
2476 seen[d as usize] = true;
2477 stack.push(d);
2478 }
2479 }
2480 }
2481 }
2482 reps
2483}
2484
2485/// How many orbits the corners fall into under these generators.
2486pub fn orbit_count(n: usize, generators: &[CubeSym]) -> u64 {
2487 orbit_representatives(n, generators).len() as u64
2488}
2489
2490/// The **symmetry-broken** cover-totality check: when every generator is a verified automorphism,
2491/// the cover is total iff it covers one representative per orbit. Same verdict as [`Cover::is_total`],
2492/// but it inspects `orbit_count` corners instead of `2ⁿ`. `None` (fail-closed) when some generator is
2493/// not actually an automorphism — never a guessed answer.
2494pub fn is_total_via_orbits(cover: &Cover, generators: &[CubeSym]) -> Option<bool> {
2495 if !generators.iter().all(|g| g.is_automorphism(cover)) {
2496 return None;
2497 }
2498 let reps = orbit_representatives(cover.n, generators);
2499 Some(reps.iter().all(|&c| cover.blocks(c)))
2500}
2501
2502/// One step of the collapse curve: how many orbits remain after stacking the first `k` generators.
2503#[derive(Clone, Copy, Debug, PartialEq, Eq)]
2504pub struct CollapseStep {
2505 pub generators_used: usize,
2506 pub orbits: u64,
2507}
2508
2509/// Stack the generators one at a time and record how the orbit count shrinks — the executable answer
2510/// to "how much does each symmetry break cut the problem?" Begins at `2ⁿ` (no symmetry) and descends
2511/// as generators compose. The ratios are *measured*, not asserted.
2512pub fn collapse_curve(n: usize, generators: &[CubeSym]) -> Vec<CollapseStep> {
2513 let mut steps = Vec::with_capacity(generators.len() + 1);
2514 steps.push(CollapseStep {
2515 generators_used: 0,
2516 orbits: 1u64 << n,
2517 });
2518 for k in 1..=generators.len() {
2519 steps.push(CollapseStep {
2520 generators_used: k,
2521 orbits: orbit_count(n, &generators[..k]),
2522 });
2523 }
2524 steps
2525}
2526
2527/// The pigeonhole cover: `n` pigeons into `n-1` holes. Variable `(p,h)` ("pigeon `p` in hole `h`")
2528/// lives at index `p*(n-1)+h`, matching [`crate::families::php`]. Always buildable, always UNSAT.
2529pub fn php_cover(n: usize) -> Cover {
2530 let (cnf, _) = crate::families::php(n);
2531 Cover::of_cnf(&cnf)
2532}
2533
2534/// The generating symmetries of the pigeonhole cover: adjacent transpositions of pigeons (rows) and
2535/// of holes (columns). Together they generate the full grid symmetry group `Sₙ × Sₙ₋₁` — pure
2536/// coordinate permutations (no phase flips). Each is a [`CubeSym`] over the `n*(n-1)` grid variables.
2537pub fn php_symmetries(n: usize) -> Vec<CubeSym> {
2538 let holes = n.saturating_sub(1);
2539 let num_vars = n * holes;
2540 let var = |p: usize, h: usize| p * holes + h;
2541 let mut gens = Vec::new();
2542 // Adjacent pigeon (row) swaps.
2543 for p in 0..n.saturating_sub(1) {
2544 let mut perm: Vec<usize> = (0..num_vars).collect();
2545 for h in 0..holes {
2546 perm.swap(var(p, h), var(p + 1, h));
2547 }
2548 gens.push(CubeSym {
2549 perm,
2550 flip: vec![false; num_vars],
2551 });
2552 }
2553 // Adjacent hole (column) swaps.
2554 for h in 0..holes.saturating_sub(1) {
2555 let mut perm: Vec<usize> = (0..num_vars).collect();
2556 for p in 0..n {
2557 perm.swap(var(p, h), var(p, h + 1));
2558 }
2559 gens.push(CubeSym {
2560 perm,
2561 flip: vec![false; num_vars],
2562 });
2563 }
2564 gens
2565}
2566
2567/// Generators of the full **hyperoctahedral group** `Bₙ = (ℤ/2)ⁿ ⋊ Sₙ` — the signed permutations,
2568/// the automorphism group of the `n`-cube and the *complete* clause-level symmetry: every [`CubeSym`]
2569/// is one of its elements. The `n−1` adjacent coordinate transpositions generate `Sₙ`; the single
2570/// coordinate-0 flip, conjugated by those, generates the `(ℤ/2)ⁿ` of phase flips; together they
2571/// generate all of `Bₙ`. The [`cube_group_closure`] of these has order exactly `2ⁿ·n!`
2572/// (`1, 2, 8, 48, 384, 3840` for `n = 0..=5`). The census quotients minimal covers by this group.
2573pub fn hyperoctahedral_generators(n: usize) -> Vec<CubeSym> {
2574 let mut gens = Vec::new();
2575 for i in 0..n.saturating_sub(1) {
2576 let mut perm: Vec<usize> = (0..n).collect();
2577 perm.swap(i, i + 1);
2578 gens.push(CubeSym {
2579 perm,
2580 flip: vec![false; n],
2581 });
2582 }
2583 if n > 0 {
2584 let mut flip = vec![false; n];
2585 flip[0] = true;
2586 gens.push(CubeSym {
2587 perm: (0..n).collect(),
2588 flip,
2589 });
2590 }
2591 gens
2592}
2593
2594/// The full group generated by `generators`, materialized (closure under composition) — the public
2595/// door onto the otherwise-internal `group_closure`. For the small groups the census needs (`Bₙ`,
2596/// `n ≤ 5` ⇒ `|G| = 3840`) the orbit–stabilizer cross-checks sum over every element.
2597pub fn cube_group_closure(generators: &[CubeSym], n: usize) -> Vec<CubeSym> {
2598 group_closure(generators, n)
2599}
2600
2601/// **The minimum width of a resolution refutation of an UNSAT cover** — the size of the widest clause
2602/// any width-bounded refutation must carry, the classic resolution complexity measure (Ben-Sasson–
2603/// Wigderson). A subcube *is* a clause (`Subcube::clause_literals`) and [`Subcube::resolve`] is the
2604/// geometry of the resolution step; the empty subcube (`care = 0`, the whole cube blocked) is the
2605/// derived contradiction. For width budget `w` we seed with the input blockers of support `≤ w` and
2606/// saturate under width-`≤ w` resolution; the least `w` that derives the empty subcube is the width.
2607/// `None` only if the cover is satisfiable (no refutation at any width); every UNSAT cover succeeds by
2608/// `w = n` since full-width resolution is complete. (For small covers — it enumerates resolvents.)
2609pub fn min_resolution_width(cover: &Cover) -> Option<usize> {
2610 let n = cover.n;
2611 let empty = Subcube {
2612 n,
2613 care: 0,
2614 value: 0,
2615 };
2616 for w in 0..=n {
2617 let mut set: BTreeSet<Subcube> = cover
2618 .blockers
2619 .iter()
2620 .copied()
2621 .filter(|b| b.care.count_ones() as usize <= w)
2622 .collect();
2623 if set.contains(&empty) {
2624 return Some(w);
2625 }
2626 loop {
2627 let snapshot: Vec<Subcube> = set.iter().copied().collect();
2628 let mut added = false;
2629 for i in 0..snapshot.len() {
2630 for j in (i + 1)..snapshot.len() {
2631 if let Some((_, r)) = snapshot[i].resolve(&snapshot[j]) {
2632 if r.care.count_ones() as usize <= w && set.insert(r) {
2633 added = true;
2634 }
2635 }
2636 }
2637 }
2638 if set.contains(&empty) {
2639 return Some(w);
2640 }
2641 if !added {
2642 break;
2643 }
2644 }
2645 }
2646 None
2647}
2648
2649/// The lexicographic key of a cover — its sorted blocker list — for orbit canonicalization. Two covers
2650/// are the same set of clauses iff their keys match.
2651fn cover_key(blockers: &[Subcube]) -> Vec<Subcube> {
2652 let mut k = blockers.to_vec();
2653 k.sort_unstable();
2654 k.dedup();
2655 k
2656}
2657
2658/// The canonical key of a cover under a **materialized** group: the lexicographically least sorted
2659/// blocker list over all images `{ g·blockers : g ∈ group }`. A flat `min` over the precomputed group —
2660/// no per-call orbit BFS — so it is cheap enough to evaluate on every node of the orderly-generation
2661/// search. Constant on a `Bₙ` orbit and distinct across orbits, hence a sound orbit invariant.
2662fn canonical_key(blockers: &[Subcube], group: &[CubeSym]) -> Vec<Subcube> {
2663 group
2664 .iter()
2665 .map(|g| {
2666 cover_key(
2667 &blockers
2668 .iter()
2669 .map(|b| g.map_subcube(b))
2670 .collect::<Vec<_>>(),
2671 )
2672 })
2673 .min()
2674 .unwrap_or_else(|| cover_key(blockers))
2675}
2676
2677/// **The `Bₙ`-canonical form of a cover, and its orbit size.** Acts the group on the *whole* cover by
2678/// `g·C = { g.map_subcube(b) }` and returns the lexicographically least sorted-blocker key together with
2679/// the number of distinct covers in the orbit. The canonical key is constant on an orbit and distinct
2680/// across orbits, a sound orbit invariant; the orbit size feeds the orbit–stabilizer identity
2681/// `|Stab| · orbit_size = |Bₙ|`.
2682pub fn canonical_cover(cover: &Cover, generators: &[CubeSym]) -> (Vec<Subcube>, usize) {
2683 let group = group_closure(generators, cover.n);
2684 let images: BTreeSet<Vec<Subcube>> = group
2685 .iter()
2686 .map(|g| {
2687 cover_key(
2688 &cover
2689 .blockers
2690 .iter()
2691 .map(|b| g.map_subcube(b))
2692 .collect::<Vec<_>>(),
2693 )
2694 })
2695 .collect();
2696 let best = images
2697 .iter()
2698 .next()
2699 .cloned()
2700 .unwrap_or_else(|| cover_key(&cover.blockers));
2701 (best, images.len())
2702}
2703
2704/// **Enumerate every minimal UNSAT cover of the `n`-cube, one canonical representative per `Bₙ` orbit.**
2705/// A minimal cover is a set of subcube blockers that covers every corner (UNSAT) and *none of which is
2706/// droppable* (every blocker privately owns some corner) — i.e. a minimal unsatisfiable CNF (an MUS),
2707/// the irreducible atom of the UNSAT universe. Branch on the lex-least uncovered corner: it lies in
2708/// exactly `2ⁿ` subcubes (one per support `care ⊆ [n]`, with `value = corner & care`); recurse on each.
2709/// **Monotone pruning** kills a branch the moment any chosen blocker becomes fully redundant (it can
2710/// never recover a private corner once one is stolen). A leaf is total ∧ fully essential; leaves are
2711/// folded to their [`canonical_cover`] key so each orbit is reported once. (Exhaustive; for small `n`.)
2712pub fn minimal_cover_orbits(n: usize) -> Vec<Cover> {
2713 let generators = hyperoctahedral_generators(n);
2714 let group = group_closure(&generators, n); // the materialized Bₙ, built once and reused per node
2715 let mut orbits: HashMap<Vec<Subcube>, Cover> = HashMap::new();
2716 // **Orderly generation.** Visit each `Bₙ`-equivalence-class of partial covers exactly once, keyed
2717 // by its canonical form: expanding any representative of a class yields the same child classes (the
2718 // lex-least-uncovered corner and its covering subcubes commute with the group action), so one
2719 // representative per class still reaches every orbit leaf. This collapses both the branch-order
2720 // duplication and the up-to-`|Bₙ|` symmetric copies that otherwise make the raw tree intractable.
2721 let mut visited: BTreeSet<Vec<Subcube>> = BTreeSet::new();
2722 let mut chosen: Vec<Subcube> = Vec::new();
2723 enumerate_minimal_covers(n, &mut chosen, &group, &mut visited, &mut orbits);
2724 let mut out: Vec<Cover> = orbits.into_values().collect();
2725 out.sort_by(|a, b| cover_key(&a.blockers).cmp(&cover_key(&b.blockers)));
2726 out
2727}
2728
2729/// A blocker is *redundant* in a partial cover when every corner it blocks is also blocked by some
2730/// other chosen blocker — it owns no private corner. Used both for monotone pruning and the leaf
2731/// minimality check.
2732fn blocker_is_redundant(blockers: &[Subcube], i: usize) -> bool {
2733 blockers[i].footprint().iter().all(|&c| {
2734 blockers
2735 .iter()
2736 .enumerate()
2737 .any(|(j, b)| j != i && b.covers(c))
2738 })
2739}
2740
2741fn enumerate_minimal_covers(
2742 n: usize,
2743 chosen: &mut Vec<Subcube>,
2744 group: &[CubeSym],
2745 visited: &mut BTreeSet<Vec<Subcube>>,
2746 orbits: &mut HashMap<Vec<Subcube>, Cover>,
2747) {
2748 // Monotone minimality: if any chosen blocker is already fully redundant, no extension is minimal.
2749 if (0..chosen.len()).any(|i| blocker_is_redundant(chosen, i)) {
2750 return;
2751 }
2752 // Orderly generation: skip this partial if a symmetric copy (same canonical class) was already
2753 // expanded — every orbit it could reach is reachable from that copy.
2754 let canon = canonical_key(chosen, group);
2755 if !visited.insert(canon.clone()) {
2756 return;
2757 }
2758 let cover = Cover {
2759 n,
2760 blockers: chosen.clone(),
2761 };
2762 match cover.escaping_corner() {
2763 None => {
2764 // Total. By the monotone check above, every blocker is essential — a genuine minimal cover.
2765 // Its canonical key is the partial's canonical key (already computed).
2766 orbits.entry(canon).or_insert(cover);
2767 }
2768 Some(c) => {
2769 // Branch over the subcubes that contain the lex-least uncovered corner `c`: a subcube
2770 // contains `c` iff `value = c & care`, and every `care ⊆ [n]` is an integer in `0..2ⁿ`. We
2771 // start at `care = 1` to exclude the degenerate `care = 0` whole-cube blocker — the empty
2772 // clause `⊥`, which carries no variable structure and is the *only* minimal cover it can
2773 // belong to (it makes every other blocker redundant). The census is over genuine CNF: every
2774 // clause mentions at least one variable.
2775 for care in 1u64..(1u64 << n) {
2776 let blocker = Subcube {
2777 n,
2778 care,
2779 value: c & care,
2780 };
2781 if !chosen.contains(&blocker) {
2782 chosen.push(blocker);
2783 enumerate_minimal_covers(n, chosen, group, visited, orbits);
2784 chosen.pop();
2785 }
2786 }
2787 }
2788 }
2789}
2790
2791#[cfg(test)]
2792#[path = "../../logicaffeine_tests/unit/logicaffeine_proof/hypercube/tests.rs"]
2793mod tests;