Skip to main content

logicaffeine_proof/
lll.rs

1//! Satisfiability **from sparsity** — the Lovász Local Lemma certificate and its constructive
2//! Moser–Tardos witness. The lower bookend to the first-moment bound.
3//!
4//! The first-moment bound ([`crate::families::ksat_threshold_first_moment_upper`]) says: *above* a clause
5//! density the expected number of solutions vanishes, so the formula is UNSAT with high probability. This
6//! module is the opposite side: a formula that is *locally sparse* — every clause shares variables with
7//! few others — is **satisfiable**, and the witness can be **constructed**.
8//!
9//! Symmetric LLL: a uniform random assignment violates a width-`w` clause with probability `2⁻ʷ`. If each
10//! clause shares a variable with at most `d` others and `e · p · (d+1) ≤ 1` (where `p = 2^{−w_min}` is the
11//! worst-case violation probability), then some assignment satisfies *all* clauses. This is:
12//! - **sound** — the LLL theorem (and we fuzz it against brute force: a certificate never lies);
13//! - **re-checkable** — recompute `w_min` and `d`;
14//! - **constructive** — Moser–Tardos resampling reaches a model in expected `O(m)` steps under the
15//!   condition, so the certificate is also a *witness recipe*.
16
17use crate::cdcl::Lit;
18
19/// A re-checkable SAT certificate from the Lovász Local Lemma: the minimum clause width `w_min` and the
20/// maximum dependency degree `d` that together satisfy `e · 2^{−w_min} · (d+1) ≤ 1`.
21#[derive(Clone, Copy, Debug, PartialEq, Eq)]
22pub struct LllSatCert {
23    pub min_width: usize,
24    pub max_degree: usize,
25}
26
27/// The LLL **dependency degree**: the maximum, over all clauses, of the number of *other* clauses that
28/// share at least one variable with it. Clauses over disjoint variable sets are independent events and do
29/// not count toward the degree.
30pub fn lll_dependency_degree(clauses: &[Vec<Lit>]) -> usize {
31    use std::collections::{HashMap, HashSet};
32    let mut occ: HashMap<u32, Vec<usize>> = HashMap::new();
33    for (i, c) in clauses.iter().enumerate() {
34        for l in c {
35            occ.entry(l.var()).or_default().push(i);
36        }
37    }
38    let mut max_d = 0;
39    for (i, c) in clauses.iter().enumerate() {
40        let mut neigh: HashSet<usize> = HashSet::new();
41        for l in c {
42            for &j in &occ[&l.var()] {
43                if j != i {
44                    neigh.insert(j);
45                }
46            }
47        }
48        max_d = max_d.max(neigh.len());
49    }
50    max_d
51}
52
53/// Certify satisfiability from sparsity via the symmetric LLL. Returns the witnessing degrees when
54/// `e · 2^{−w_min} · (d+1) ≤ 1`; otherwise `None` (the condition is *sufficient, not necessary* — `None`
55/// means "this certificate does not apply", never "UNSAT"). An empty clause set is vacuously SAT; a set
56/// containing an empty clause can never be certified (it is UNSAT).
57pub fn lll_certifies_sat(clauses: &[Vec<Lit>]) -> Option<LllSatCert> {
58    if clauses.is_empty() {
59        return Some(LllSatCert {
60            min_width: usize::MAX,
61            max_degree: 0,
62        });
63    }
64    let min_width = clauses.iter().map(|c| c.len()).min().unwrap();
65    if min_width == 0 {
66        return None; // an empty clause is unsatisfiable
67    }
68    let d = lll_dependency_degree(clauses);
69    let p = 2f64.powi(-(min_width as i32));
70    if std::f64::consts::E * p * (d as f64 + 1.0) <= 1.0 {
71        Some(LllSatCert {
72            min_width,
73            max_degree: d,
74        })
75    } else {
76        None
77    }
78}
79
80/// Constructively find a satisfying assignment by **Moser–Tardos resampling**: start from a random
81/// assignment and, while some clause is violated, resample the variables of one violated clause. Under
82/// the LLL condition this terminates in expected `O(m)` resamples; the `max_resamples` cap is a safety
83/// net (only reachable when the condition does not hold). Returns a model, or `None` if the cap is hit.
84pub fn moser_tardos_witness(
85    num_vars: usize,
86    clauses: &[Vec<Lit>],
87    seed: u64,
88    max_resamples: usize,
89) -> Option<Vec<bool>> {
90    let mut rng = seed;
91    let mut next = move || {
92        rng = rng.wrapping_add(0x9E3779B97F4A7C15);
93        let mut z = rng;
94        z = (z ^ (z >> 30)).wrapping_mul(0xBF58476D1CE4E5B9);
95        z = (z ^ (z >> 27)).wrapping_mul(0x94D049BB133111EB);
96        z ^ (z >> 31)
97    };
98    let mut assign: Vec<bool> = (0..num_vars).map(|_| next() & 1 == 0).collect();
99    let violated = |a: &[bool], c: &[Lit]| c.iter().all(|l| a[l.var() as usize] != l.is_positive());
100    for _ in 0..max_resamples {
101        match clauses.iter().find(|c| violated(&assign, c)) {
102            None => return Some(assign),
103            Some(c) => {
104                for l in c {
105                    assign[l.var() as usize] = next() & 1 == 0;
106                }
107            }
108        }
109    }
110    clauses
111        .iter()
112        .all(|c| !violated(&assign, c))
113        .then_some(assign)
114}
115
116#[cfg(test)]
117#[path = "../../logicaffeine_tests/unit/logicaffeine_proof/lll/tests.rs"]
118mod tests;