problemreductions/rules/
subsetsum_closestvectorproblem.rs

1//! Reduction from Subset Sum to CVP using binary carry equations.
2
3use crate::models::algebraic::ClosestVectorProblem;
4use crate::models::misc::SubsetSum;
5use crate::reduction;
6use crate::registry::ConstructionError;
7use crate::rules::traits::{ReduceTo, ReductionResult};
8use crate::types::{Min, Or};
9
10/// Result of reducing SubsetSum to ClosestVectorProblem.
11#[derive(Debug, Clone)]
12pub struct ReductionSubsetSumToClosestVectorProblem {
13    target: ClosestVectorProblem<i64>,
14    num_elements: usize,
15    target_distance: f64,
16}
17
18impl ReductionResult for ReductionSubsetSumToClosestVectorProblem {
19    type Source = SubsetSum;
20    type Target = ClosestVectorProblem<i64>;
21
22    fn target_problem(&self) -> &Self::Target {
23        &self.target
24    }
25
26    fn extract_solution(
27        &self,
28        target_solution: &<Self::Target as crate::traits::Problem>::Solution,
29    ) -> crate::rules::ExtractionResult<<Self::Source as crate::traits::Problem>::Solution> {
30        let value =
31            crate::rules::traits::validate_target_solution(self.target_problem(), target_solution)?;
32        let certificate = crate::rules::AggregateReductionResult::extract_value(self, value);
33        if !certificate.0 {
34            return Err(crate::rules::ExtractionError::invalid(
35                "target lattice vector does not certify a subset sum",
36            ));
37        }
38        Ok(target_solution[..self.num_elements]
39            .iter()
40            .map(|&value| value == 1)
41            .collect())
42    }
43}
44
45impl crate::rules::AggregateReductionResult for ReductionSubsetSumToClosestVectorProblem {
46    type Source = SubsetSum;
47    type Target = ClosestVectorProblem<i64>;
48
49    fn target_problem(&self) -> &Self::Target {
50        &self.target
51    }
52
53    fn extract_value(&self, target_value: Min<f64>) -> Or {
54        Or(target_value == Min(Some(self.target_distance)))
55    }
56}
57
58impl ReductionSubsetSumToClosestVectorProblem {
59    /// Check the dense representation before allocating its columns.
60    fn dimensions(
61        num_elements: usize,
62        bit_width: u64,
63    ) -> Result<(usize, usize, usize), crate::rules::ReductionError> {
64        let overflow = || {
65            crate::rules::ReductionError::integer_overflow::<SubsetSum, ClosestVectorProblem<i64>>(
66                "sizing the binary-carry lattice",
67            )
68        };
69        let bits = usize::try_from(bit_width).map_err(|_| overflow())?;
70        let carries = bits.checked_sub(1).ok_or_else(overflow)?;
71        let columns = num_elements.checked_add(carries).ok_or_else(overflow)?;
72        let rows = columns
73            .checked_add(num_elements)
74            .and_then(|value| value.checked_add(1))
75            .ok_or_else(overflow)?;
76        rows.checked_mul(columns)
77            .and_then(|entries| entries.checked_mul(std::mem::size_of::<i64>()))
78            .ok_or_else(overflow)?;
79        Ok((bits, rows, columns))
80    }
81}
82
83#[reduction(
84    aggregate = custom,
85    transform = unavailable {
86        ambient_dimension = "2n+b depends on input bit length b, which is not a registered SubsetSum parameter",
87        num_basis_vectors = "n+b-1 depends on input bit length b, which is not a registered SubsetSum parameter",
88    },
89)]
90impl ReduceTo<ClosestVectorProblem<i64>> for SubsetSum {
91    type Result = ReductionSubsetSumToClosestVectorProblem;
92
93    fn reduce_to(&self) -> Result<Self::Result, crate::rules::ReductionError> {
94        let n = self.num_elements();
95        let bit_width = self
96            .sizes()
97            .iter()
98            .fold(self.target().bits().max(1), |bits, size| {
99                bits.max(size.bits())
100            });
101        let (bits, rows, columns) =
102            ReductionSubsetSumToClosestVectorProblem::dimensions(n, bit_width)?;
103        let mut basis = Vec::with_capacity(columns);
104        // Paired residuals x_i and x_i-1 have minimum squared contribution one,
105        // attained exactly at 0 and 1. Their leading identity gives unit pivots.
106        for (i, size) in self.sizes().iter().enumerate() {
107            let mut column = vec![0_i64; rows];
108            column[i] = 1;
109            column[n + i] = 1;
110            for bit in 0..bits {
111                column[rows - 1 - bit] = i64::from(size.bit(bit as u64));
112            }
113            basis.push(column);
114        }
115        // Carry c_k occurs with +1 in bit k and -2 in bit k-1. Descending
116        // bit rows and carry columns preserve unit pivots in the formal rank
117        // checker, without changing its implementation or bypassing validation.
118        for bit in (1..bits).rev() {
119            let mut column = vec![0_i64; rows];
120            column[rows - 1 - bit] = 1;
121            column[rows - bit] = -2;
122            basis.push(column);
123        }
124        let mut target = vec![0_i64; rows];
125        target[n..2 * n].fill(1);
126        for bit in 0..bits {
127            target[rows - 1 - bit] = i64::from(self.target().bit(bit as u64));
128        }
129        // The checked dense byte count bounds n below 2^30 on 64-bit systems,
130        // so the integer threshold and its unit squared-distance gap are exact.
131        let count = <Self as ReduceTo<ClosestVectorProblem<i64>>>::exact_i64(
132            n,
133            "representing the subset-sum distance threshold",
134        )?;
135        let target_distance = crate::types::i64_to_exact_f64(count)
136            .map_err(ConstructionError::from)
137            .map_err(<Self as ReduceTo<ClosestVectorProblem<i64>>>::target_construction)?
138            .sqrt();
139        let target = ClosestVectorProblem::new(basis, target)
140            .map_err(<Self as ReduceTo<ClosestVectorProblem<i64>>>::target_construction)?;
141        Ok(ReductionSubsetSumToClosestVectorProblem {
142            target,
143            num_elements: n,
144            target_distance,
145        })
146    }
147}
148
149#[cfg(feature = "example-db")]
150pub(crate) fn canonical_rule_example_specs() -> Vec<crate::example_db::specs::RuleExampleSpec> {
151    use crate::export::SolutionPair;
152
153    vec![crate::example_db::specs::RuleExampleSpec {
154        id: "subsetsum_to_closestvectorproblem",
155        build: || {
156            crate::example_db::specs::rule_example_with_witness::<_, ClosestVectorProblem<i64>>(
157                SubsetSum::new(vec![3u32, 7, 1, 8], 11u32),
158                SolutionPair {
159                    source_config: serde_json::json!(vec![true, false, false, true]),
160                    target_config: serde_json::json!(vec![1, 0, 0, 1, 0, 0, 0]),
161                },
162            )
163        },
164    }]
165}
166
167#[cfg(test)]
168#[path = "../unit_tests/rules/subsetsum_closestvectorproblem.rs"]
169mod tests;
problemreductions/rules/subsetsum_closestvectorproblem.rs

problemreductions/rules/
subsetsum_closestvectorproblem.rs
