logicaffeine_proof/ordering.rs
1//! The **ordering-principle specialist** — a polynomial-time recognizer + refuter for GT(n), the
2//! linear-ordering contradiction. GT(n) asserts a strict total order (totality + antisymmetry +
3//! transitivity) in which every element has a strictly greater one ("no maximum"). That is impossible:
4//! a finite strict total order always has a maximum. So a complete GT(n) core is unsatisfiable, and any
5//! formula containing it (a superset of an UNSAT core) is UNSAT.
6//!
7//! The general cascade decides GT(n) only by super-polynomial search (measured: GT(20) ≈ 2.7s, ~68k
8//! conflicts, growing ~10x every 4 steps). This module recognizes the structure directly and certifies
9//! UNSAT from it — polynomial, and instant where search walls.
10//!
11//! **Soundness** is by faithful, conservative recognition, in the style of [`crate::pigeonhole`]: the
12//! recognizer verifies, for a single consistent element/edge identification, that ALL of totality,
13//! antisymmetry, transitivity (every ordered triple), and the no-maximum clause (every element) are
14//! present. Only then is a complete GT(n) core certified present — and it is genuinely UNSAT. Any
15//! missing, ambiguous, or extra-shaped piece makes the recognizer return `None` (never a false
16//! refutation); the caller then falls through to the general engine. Full transitivity is essential:
17//! without it a "no-maximum tournament" can be a satisfiable cycle (e.g. 0<1<2<0), so an incomplete
18//! structure must not be refuted.
19//!
20//! The refutation object is an [`OrderingCert`]: the element/edge identification, which a checker
21//! re-verifies against the raw clauses ([`check_ordering_cert`]) with zero trust in how it was produced.
22
23use crate::cdcl::Lit;
24use std::collections::{HashMap, HashSet};
25
26/// A re-checkable ordering-principle refutation: the recovered element/edge identification of a complete
27/// GT(n) core. `edge[i * n + j]` is the comparison variable `x_ij` ("i < j") for the ordered pair
28/// `(i, j)`; diagonal entries (`i == j`) are [`u32::MAX`] and unused. Given this map a checker
29/// re-verifies that every totality, antisymmetry, transitivity, and no-maximum clause is present — the
30/// whole certificate, no trust in the recognizer.
31#[derive(Clone, Debug, PartialEq, Eq)]
32pub struct OrderingCert {
33 /// The number of ordered elements.
34 pub n: usize,
35 /// The comparison variable `x_ij` at flat index `i * n + j` (diagonal = `u32::MAX`).
36 pub edge: Vec<u32>,
37}
38
39impl OrderingCert {
40 fn get(&self, i: usize, j: usize) -> u32 {
41 self.edge[i * self.n + j]
42 }
43
44 /// The serialized size in bytes: the element count plus one 32-bit variable id per off-diagonal
45 /// ordered pair — the `O(n²)` identification a checker consumes.
46 pub fn byte_len(&self) -> usize {
47 8 + self.n * (self.n - 1) * 4
48 }
49}
50
51/// Recover a complete ordering-principle (GT(n)) core from `clauses`, or `None` if there is none. On
52/// `Some(cert)` the formula is unsatisfiable (a finite strict total order has a maximum, contradicting
53/// the no-maximum clauses), and `cert` re-checks via [`check_ordering_cert`]. Conservative / fail-closed
54/// — never a false certificate. See the module docs.
55pub fn ordering_certificate(num_vars: usize, clauses: &[Vec<Lit>]) -> Option<OrderingCert> {
56 if num_vars < 2 {
57 return None;
58 }
59 let key2 = |x: u32, y: u32| if x < y { (x, y) } else { (y, x) };
60
61 // ---- 1. Index clauses by shape. ----
62 // {a,b} both positive → totality candidate; {a,b} both negative → antisymmetry candidate;
63 // [¬a, ¬b, c] → transitivity; any all-positive clause → no-maximum candidate.
64 let mut pos2: HashSet<(u32, u32)> = HashSet::new();
65 let mut neg2: HashSet<(u32, u32)> = HashSet::new();
66 let mut trans: HashSet<(u32, u32, u32)> = HashSet::new(); // (a, b, c) for the clause ¬a ∨ ¬b ∨ c
67 let mut positive_clauses: Vec<Vec<u32>> = Vec::new();
68 for c in clauses {
69 if c.iter().all(|l| l.is_positive()) {
70 positive_clauses.push(c.iter().map(|l| l.var()).collect());
71 }
72 match c.len() {
73 2 => match (c[0].is_positive(), c[1].is_positive()) {
74 (true, true) => {
75 pos2.insert(key2(c[0].var(), c[1].var()));
76 }
77 (false, false) => {
78 neg2.insert(key2(c[0].var(), c[1].var()));
79 }
80 _ => {}
81 },
82 3 => {
83 let negs: Vec<u32> = c
84 .iter()
85 .filter(|l| !l.is_positive())
86 .map(|l| l.var())
87 .collect();
88 let poss: Vec<u32> = c
89 .iter()
90 .filter(|l| l.is_positive())
91 .map(|l| l.var())
92 .collect();
93 if negs.len() == 2 && poss.len() == 1 {
94 trans.insert((negs[0], negs[1], poss[0]));
95 trans.insert((negs[1], negs[0], poss[0]));
96 }
97 }
98 _ => {}
99 }
100 }
101
102 // ---- 2. Comparison pairs: {a,b} carrying BOTH totality and antisymmetry (the two directions of one
103 // element pair). Every comparison variable must belong to exactly one such pair. ----
104 let comparisons: Vec<(u32, u32)> = pos2.intersection(&neg2).copied().collect();
105 if comparisons.len() < 2 {
106 return None;
107 }
108 let mut partner: HashMap<u32, u32> = HashMap::new();
109 for &(a, b) in &comparisons {
110 if partner.insert(a, b).is_some() || partner.insert(b, a).is_some() {
111 return None; // a variable in two comparison pairs — not a clean ordering encoding
112 }
113 }
114 let comparison_vars: HashSet<u32> = partner.keys().copied().collect();
115
116 // ---- 3. No-maximum clauses partition the comparison variables into per-element OUTGOING groups. A
117 // no-maximum clause for element i is {x_ij : j≠i}: all positive comparison variables, pairwise
118 // NON-partners. A totality clause [x_ij, x_ji] is positive too, but its vars ARE partners. ----
119 let mut groups: Vec<Vec<u32>> = Vec::new();
120 let mut group_of: HashMap<u32, usize> = HashMap::new();
121 for pc in &positive_clauses {
122 if pc.is_empty() || !pc.iter().all(|v| comparison_vars.contains(v)) {
123 continue;
124 }
125 let set: HashSet<u32> = pc.iter().copied().collect();
126 if set.len() != pc.len() {
127 continue; // a repeated variable
128 }
129 if pc.iter().any(|v| set.contains(&partner[v])) {
130 continue; // contains a comparison pair → a totality clause, not a no-maximum clause
131 }
132 if pc.iter().any(|v| group_of.contains_key(v)) {
133 continue; // overlaps an already-claimed group — require a clean partition
134 }
135 let gid = groups.len();
136 for &v in pc {
137 group_of.insert(v, gid);
138 }
139 groups.push(pc.clone());
140 }
141 let n = groups.len();
142 if n < 2
143 || group_of.len() != comparison_vars.len()
144 || comparison_vars.len() != n * (n - 1)
145 || groups.iter().any(|g| g.len() != n - 1)
146 {
147 return None;
148 }
149
150 // ---- 4. Directed edge map: edge[(i,j)] = x_ij. For a comparison pair {a,b}, a lies in group i and
151 // b in group j, so a is the i→j edge and b the j→i edge. ----
152 let mut edge_map: HashMap<(usize, usize), u32> = HashMap::new();
153 for (&a, &b) in &partner {
154 let (i, j) = (group_of[&a], group_of[&b]);
155 if i == j || edge_map.insert((i, j), a).is_some() {
156 return None; // partner within one element, or two edges for the same ordered pair
157 }
158 }
159 if edge_map.len() != n * (n - 1) {
160 return None;
161 }
162 let mut edge = vec![u32::MAX; n * n];
163 for i in 0..n {
164 for j in 0..n {
165 if i == j {
166 continue;
167 }
168 match edge_map.get(&(i, j)) {
169 Some(&v) => edge[i * n + j] = v,
170 None => return None, // a missing directed comparison — not a complete tournament
171 }
172 }
173 }
174 // each group must be EXACTLY element i's outgoing set {edge[(i,j)] : j≠i}.
175 for (i, g) in groups.iter().enumerate() {
176 let expected: HashSet<u32> = (0..n)
177 .filter(|&j| j != i)
178 .map(|j| edge[i * n + j])
179 .collect();
180 if expected != g.iter().copied().collect() {
181 return None;
182 }
183 }
184
185 // ---- 5. Verify COMPLETE transitivity: every ordered distinct triple (i,j,k) has ¬x_ij ∨ ¬x_jk ∨
186 // x_ik. Essential for soundness — a tournament missing transitivity can be a satisfiable cycle. ----
187 for i in 0..n {
188 for j in 0..n {
189 if j == i {
190 continue;
191 }
192 for k in 0..n {
193 if k == i || k == j {
194 continue;
195 }
196 if !trans.contains(&(edge[i * n + j], edge[j * n + k], edge[i * n + k])) {
197 return None;
198 }
199 }
200 }
201 }
202
203 Some(OrderingCert { n, edge })
204}
205
206/// Re-check an [`OrderingCert`] against the raw `clauses` from scratch, trusting nothing about how it was
207/// produced: verify that for its element/edge identification EVERY totality, antisymmetry, transitivity,
208/// and no-maximum clause is present. `true` iff the certificate genuinely witnesses a complete GT(n)
209/// core (which is unsatisfiable), so the formula is UNSAT.
210pub fn check_ordering_cert(cert: &OrderingCert, clauses: &[Vec<Lit>]) -> bool {
211 let n = cert.n;
212 if n < 2 || cert.edge.len() != n * n {
213 return false;
214 }
215 // every off-diagonal edge is a real variable, and the n·(n−1) of them are distinct.
216 let mut seen = HashSet::new();
217 for i in 0..n {
218 for j in 0..n {
219 if i == j {
220 continue;
221 }
222 let v = cert.get(i, j);
223 if v == u32::MAX || !seen.insert(v) {
224 return false;
225 }
226 }
227 }
228 // build clause lookups.
229 let key2 = |x: u32, y: u32| if x < y { (x, y) } else { (y, x) };
230 let mut pos2 = HashSet::new();
231 let mut neg2 = HashSet::new();
232 let mut trans = HashSet::new();
233 let mut positive: HashSet<Vec<u32>> = HashSet::new();
234 for c in clauses {
235 if c.iter().all(|l| l.is_positive()) {
236 let mut vs: Vec<u32> = c.iter().map(|l| l.var()).collect();
237 vs.sort_unstable();
238 positive.insert(vs);
239 }
240 match c.len() {
241 2 => match (c[0].is_positive(), c[1].is_positive()) {
242 (true, true) => {
243 pos2.insert(key2(c[0].var(), c[1].var()));
244 }
245 (false, false) => {
246 neg2.insert(key2(c[0].var(), c[1].var()));
247 }
248 _ => {}
249 },
250 3 => {
251 let negs: Vec<u32> = c
252 .iter()
253 .filter(|l| !l.is_positive())
254 .map(|l| l.var())
255 .collect();
256 let poss: Vec<u32> = c
257 .iter()
258 .filter(|l| l.is_positive())
259 .map(|l| l.var())
260 .collect();
261 if negs.len() == 2 && poss.len() == 1 {
262 trans.insert((negs[0], negs[1], poss[0]));
263 }
264 }
265 _ => {}
266 }
267 }
268 // totality + antisymmetry for every unordered pair.
269 for i in 0..n {
270 for j in (i + 1)..n {
271 let (a, b) = (cert.get(i, j), cert.get(j, i));
272 if !pos2.contains(&key2(a, b)) || !neg2.contains(&key2(a, b)) {
273 return false;
274 }
275 }
276 }
277 // transitivity for every ordered distinct triple.
278 for i in 0..n {
279 for j in 0..n {
280 if j == i {
281 continue;
282 }
283 for k in 0..n {
284 if k == i || k == j {
285 continue;
286 }
287 let want = (cert.get(i, j), cert.get(j, k), cert.get(i, k));
288 let alt = (cert.get(j, k), cert.get(i, j), cert.get(i, k));
289 if !trans.contains(&want) && !trans.contains(&alt) {
290 return false;
291 }
292 }
293 }
294 }
295 // no-maximum clause for every element (its complete outgoing set, in sorted order).
296 for i in 0..n {
297 let mut out: Vec<u32> = (0..n).filter(|&j| j != i).map(|j| cert.get(i, j)).collect();
298 out.sort_unstable();
299 if !positive.contains(&out) {
300 return false;
301 }
302 }
303 true
304}
305
306/// Refute a formula that contains a complete ordering-principle core. `true` iff a certificate is
307/// recovered — see [`ordering_certificate`]. Never a false refutation.
308pub fn refute_ordering(num_vars: usize, clauses: &[Vec<Lit>]) -> bool {
309 ordering_certificate(num_vars, clauses).is_some()
310}
311
312/// The ordering cut over a `ProofExpr`: clausify and run the specialist. This is the entry the cascade
313/// ([`crate::sat::prove_unsat`]) calls.
314pub fn refutes_ordering_principle(e: &crate::ProofExpr) -> bool {
315 let mut cnf = crate::cnf::Cnf::new();
316 if cnf.assert(e).is_none() {
317 return false;
318 }
319 refute_ordering(cnf.num_vars(), cnf.clauses())
320}