Skip to main content

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}