problemreductions/models/misc/
cosine_product_integration.rs

1//! Cosine Product Integration problem implementation.
2//!
3//! Given integer frequencies `a_1, ..., a_n`, determine whether a sign
4//! assignment `ε ∈ {-1, +1}^n` exists with `∑ εᵢ aᵢ = 0`.
5//!
6//! This is equivalent to asking whether
7//! `∫₀²π ∏ᵢ cos(aᵢ θ) dθ ≠ 0` (Garey & Johnson A7 AN14).
8//! The integral is nonzero exactly when such a balanced sign assignment
9//! exists, so the G&J question "does the integral equal zero?" is the
10//! complement of this satisfaction problem.
11
12use crate::registry::{FieldInfo, ProblemSchemaEntry};
13use crate::traits::Problem;
14use serde::{Deserialize, Serialize};
15
16inventory::submit! {
17    ProblemSchemaEntry {
18        name: "CosineProductIntegration",
19        display_name: "Cosine Product Integration",
20        aliases: &[],
21        dimensions: &[],
22        module_path: module_path!(),
23        description: "Decide whether a balanced sign assignment exists for a sequence of integer frequencies",
24        fields: &[
25            FieldInfo {
26                name: "coefficients",
27                type_name: "Vec<i64>",
28                description: "Integer cosine frequencies",
29            },
30        ],
31    }
32}
33
34/// The Cosine Product Integration problem.
35///
36/// Given integer coefficients `a_1, ..., a_n`, determine whether there
37/// exists a sign assignment `ε ∈ {-1, +1}^n` with `∑ εᵢ aᵢ = 0`.
38///
39/// # Representation
40///
41/// Each variable chooses a sign: `0` means `+aᵢ`, `1` means `−aᵢ`.
42/// A configuration is satisfying when the resulting signed sum is zero.
43///
44/// # Example
45///
46/// ```
47/// use problemreductions::models::misc::CosineProductIntegration;
48/// use problemreductions::{Problem, Solver, BruteForce};
49///
50/// // coefficients [2, 3, 5]: sign assignment (+2, +3, -5) = 0
51/// let problem = CosineProductIntegration::new(vec![2, 3, 5]);
52/// let solver = BruteForce::new();
53/// let solution = solver.find_witness(&problem);
54/// assert!(solution.is_some());
55/// ```
56#[derive(Debug, Clone, Serialize, Deserialize)]
57pub struct CosineProductIntegration {
58    coefficients: Vec<i64>,
59}
60
61impl CosineProductIntegration {
62    /// Create a new CosineProductIntegration instance.
63    ///
64    /// # Panics
65    ///
66    /// Panics if `coefficients` is empty.
67    pub fn new(coefficients: Vec<i64>) -> Self {
68        assert!(
69            !coefficients.is_empty(),
70            "CosineProductIntegration requires at least one coefficient"
71        );
72        Self { coefficients }
73    }
74
75    /// Returns the cosine coefficients.
76    pub fn coefficients(&self) -> &[i64] {
77        &self.coefficients
78    }
79
80    /// Returns the number of coefficients.
81    pub fn num_coefficients(&self) -> usize {
82        self.coefficients.len()
83    }
84}
85
86impl Problem for CosineProductIntegration {
87    const NAME: &'static str = "CosineProductIntegration";
88    type Value = crate::types::Or;
89
90    fn variant() -> Vec<(&'static str, &'static str)> {
91        crate::variant_params![]
92    }
93
94    fn dims(&self) -> Vec<usize> {
95        vec![2; self.num_coefficients()]
96    }
97
98    fn evaluate(&self, config: &[usize]) -> crate::types::Or {
99        crate::types::Or({
100            if config.len() != self.num_coefficients() {
101                return crate::types::Or(false);
102            }
103            if config.iter().any(|&v| v >= 2) {
104                return crate::types::Or(false);
105            }
106            let signed_sum: i128 = self
107                .coefficients
108                .iter()
109                .zip(config.iter())
110                .map(|(&a, &bit)| {
111                    let val = a as i128;
112                    if bit == 0 {
113                        val
114                    } else {
115                        -val
116                    }
117                })
118                .sum();
119            signed_sum == 0
120        })
121    }
122}
123
124crate::declare_variants! {
125    default CosineProductIntegration => "2^(num_coefficients / 2)",
126}
127
128#[cfg(feature = "example-db")]
129pub(crate) fn canonical_model_example_specs() -> Vec<crate::example_db::specs::ModelExampleSpec> {
130    vec![crate::example_db::specs::ModelExampleSpec {
131        id: "cosine_product_integration",
132        instance: Box::new(CosineProductIntegration::new(vec![2, 3, 5])),
133        optimal_config: vec![0, 0, 1],
134        optimal_value: serde_json::json!(true),
135    }]
136}
137
138#[cfg(test)]
139#[path = "../../unit_tests/models/misc/cosine_product_integration.rs"]
140mod tests;
problemreductions/models/misc/cosine_product_integration.rs

problemreductions/models/misc/
cosine_product_integration.rs
