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;