problemreductions/rules/
threedimensionalmatching_minimumweightdecoding.rs

1//! Reduction from ThreeDimensionalMatching to MinimumWeightDecoding.
2//!
3//! This is the classical Berlekamp–McEliece–van Tilborg (1978) construction
4//! (Garey & Johnson MS7) that establishes NP-hardness of the minimum-weight
5//! codeword problem. Each triple `t_j = (a_j, b_j, c_j)` becomes a column of
6//! a `3q × m` parity-check matrix `H` with exactly three 1s (one per row
7//! block `W`, `X`, `Y`), and the syndrome is the all-ones vector `1^{3q}`.
8//!
9//! **Bridge.** This is a *witness* reduction from `ThreeDimensionalMatching`
10//! (`Value = Or`) to `MinimumWeightDecoding` (`Value = Min<usize>`):
11//!
12//! `source.evaluate(S) == Or(true)` ⇔ `target.evaluate(x) == Min(Some(q))`,
13//!
14//! where `S = { t_j ∈ T : x_j = 1 }`. We rely on the witness-extraction
15//! route `source.evaluate(extract_solution(x))` rather than comparing the
16//! optimum value directly, mirroring `partition_sumofsquarespartition.rs`.
17//!
18//! **Sentinel branch.** `MinimumWeightDecoding::new` panics on zero-row or
19//! zero-column matrices, so degenerate inputs (`q = 0` or `T = []`) emit a
20//! fixed `1×1` sentinel `H = [[1]]` with syndrome `s = [0]`. The unique
21//! feasible codeword `x = (0)` decodes to the empty subset `S = ∅`, and
22//! `source.evaluate(∅)` correctly returns `Or(true)` iff `q = 0`.
23
24use crate::models::algebraic::MinimumWeightDecoding;
25use crate::models::set::ThreeDimensionalMatching;
26use crate::reduction;
27use crate::rules::traits::{ReduceTo, ReductionResult};
28
29/// Result of reducing ThreeDimensionalMatching to MinimumWeightDecoding.
30#[derive(Debug, Clone)]
31pub struct ReductionThreeDimensionalMatchingToMinimumWeightDecoding {
32    target: MinimumWeightDecoding,
33    /// Number of triples in the original 3DM instance.
34    /// Used to return a correctly-sized witness when the sentinel path is
35    /// taken (i.e. `q == 0` or `num_triples == 0`).
36    source_num_triples: usize,
37}
38
39impl ReductionResult for ReductionThreeDimensionalMatchingToMinimumWeightDecoding {
40    type Source = ThreeDimensionalMatching;
41    type Target = MinimumWeightDecoding;
42
43    fn target_problem(&self) -> &Self::Target {
44        &self.target
45    }
46
47    /// Solution extraction: identity mapping in the main branch. The target
48    /// codeword `x ∈ {0,1}^m` is the source subset indicator over the same
49    /// triple index set. In the sentinel branch the target witness has length
50    /// `1` (always `[0]`); we return the all-zero source-sized vector,
51    /// which decodes to `S = ∅`. `ThreeDimensionalMatching::evaluate(∅)`
52    /// then yields `Or(true)` iff `q == 0` (the correct answer for both
53    /// sentinel sub-cases).
54    fn extract_solution(&self, target_solution: &[usize]) -> Vec<usize> {
55        if target_solution.len() == self.source_num_triples {
56            target_solution.to_vec()
57        } else {
58            vec![0; self.source_num_triples]
59        }
60    }
61}
62
63#[reduction(overhead = {
64    num_rows = "3 * universe_size",
65    num_cols = "num_triples",
66})]
67impl ReduceTo<MinimumWeightDecoding> for ThreeDimensionalMatching {
68    type Result = ReductionThreeDimensionalMatchingToMinimumWeightDecoding;
69
70    fn reduce_to(&self) -> Self::Result {
71        let q = self.universe_size();
72        let m = self.num_triples();
73
74        if q == 0 || m == 0 {
75            // Sentinel: MinimumWeightDecoding::new panics on empty matrices
76            // or zero-column matrices. Build a fixed 1×1 instance whose only
77            // feasible codeword is x = (0), decoding to S = ∅. The source's
78            // own evaluate on the empty set gives the correct answer:
79            //   q = 0 → Or(true)  (empty matching of empty universe)
80            //   q ≥ 1 → Or(false) (no triples cannot cover non-empty universe).
81            return ReductionThreeDimensionalMatchingToMinimumWeightDecoding {
82                target: MinimumWeightDecoding::new(vec![vec![true]], vec![false]),
83                source_num_triples: m,
84            };
85        }
86
87        // Main branch: build H ∈ {0,1}^{3q × m} with row blocks W, X, Y and
88        // one 1 per row block per column at the triple's coordinate.
89        let num_rows = 3 * q;
90        let mut matrix = vec![vec![false; m]; num_rows];
91        for (j, &(a, b, c)) in self.triples().iter().enumerate() {
92            matrix[a][j] = true;
93            matrix[q + b][j] = true;
94            matrix[2 * q + c][j] = true;
95        }
96        let syndrome = vec![true; num_rows];
97
98        ReductionThreeDimensionalMatchingToMinimumWeightDecoding {
99            target: MinimumWeightDecoding::new(matrix, syndrome),
100            source_num_triples: m,
101        }
102    }
103}
104
105#[cfg(feature = "example-db")]
106pub(crate) fn canonical_rule_example_specs() -> Vec<crate::example_db::specs::RuleExampleSpec> {
107    use crate::export::SolutionPair;
108
109    vec![crate::example_db::specs::RuleExampleSpec {
110        id: "threedimensionalmatching_to_minimumweightdecoding",
111        build: || {
112            // q = 2, T = [(0,0,0), (1,1,1), (0,1,0), (1,0,1)].
113            // Perfect matchings: {t_0, t_1} and {t_2, t_3} -- both attain
114            // target minimum weight = q = 2.
115            crate::example_db::specs::rule_example_with_witness::<_, MinimumWeightDecoding>(
116                ThreeDimensionalMatching::new(2, vec![(0, 0, 0), (1, 1, 1), (0, 1, 0), (1, 0, 1)]),
117                SolutionPair {
118                    source_config: vec![1, 1, 0, 0],
119                    target_config: vec![1, 1, 0, 0],
120                },
121            )
122        },
123    }]
124}
125
126#[cfg(test)]
127#[path = "../unit_tests/rules/threedimensionalmatching_minimumweightdecoding.rs"]
128mod tests;
problemreductions/rules/threedimensionalmatching_minimumweightdecoding.rs

problemreductions/rules/
threedimensionalmatching_minimumweightdecoding.rs
