problemreductions/models/algebraic/
algebraic_equations_over_gf2.rs

1//! Algebraic Equations over GF(2) problem implementation.
2//!
3//! Given m multilinear polynomials over GF(2) in n variables, determine whether
4//! there exists an assignment of the variables making all polynomials evaluate
5//! to 0 (mod 2).
6
7use crate::registry::{FieldInfo, ProblemSchemaEntry};
8use crate::traits::Problem;
9use crate::types::Or;
10use serde::de::Error as _;
11use serde::{Deserialize, Deserializer, Serialize};
12
13inventory::submit! {
14    ProblemSchemaEntry {
15        name: "AlgebraicEquationsOverGF2",
16        display_name: "Algebraic Equations over GF(2)",
17        aliases: &[],
18        dimensions: &[],
19        category: crate::registry::ProblemCategory::Algebraic,
20        module_path: module_path!(),
21        description: "Find assignment satisfying multilinear polynomial equations over GF(2)",
22        fields: &[
23            FieldInfo { name: "num_variables", type_name: "usize", description: "Number of Boolean variables" },
24            FieldInfo { name: "equations", type_name: "Vec<Vec<Vec<usize>>>", description: "Equations: list of polynomials, each a list of monomials, each a sorted list of variable indices" },
25        ],
26    }
27}
28
29/// Algebraic Equations over GF(2).
30///
31/// Given m multilinear polynomials over GF(2) in n variables, determine whether
32/// there exists an assignment of the variables making all polynomials evaluate
33/// to 0 (mod 2).
34///
35/// Each equation is a list of monomials. Each monomial is a sorted list of
36/// variable indices (0-indexed). An empty monomial represents the constant 1.
37/// A polynomial evaluates to 0 when the XOR (sum mod 2) of all its monomial
38/// values equals 0.
39///
40/// # Example
41///
42/// ```
43/// use problemreductions::models::algebraic::AlgebraicEquationsOverGF2;
44/// use problemreductions::{Problem, BruteForce};
45///
46/// // Two equations in 3 variables:
47/// //   x0*x1 + x2 = 0 (mod 2)
48/// //   x0 + 1 = 0 (mod 2)
49/// let problem = AlgebraicEquationsOverGF2::new(
50///     3,
51///     vec![
52///         vec![vec![0, 1], vec![2]],   // x0*x1 XOR x2
53///         vec![vec![0], vec![]],        // x0 XOR 1
54///     ],
55/// ).unwrap();
56///
57/// let solver = BruteForce::new();
58/// let witness = solver.solve(&problem).unwrap();
59/// assert!(witness.is_some());
60/// ```
61#[derive(Debug, Clone, Serialize)]
62pub struct AlgebraicEquationsOverGF2 {
63    /// Number of variables.
64    num_variables: usize,
65    /// Equations: each equation is a list of monomials;
66    /// each monomial is a sorted list of variable indices.
67    equations: Vec<Vec<Vec<usize>>>,
68}
69
70impl AlgebraicEquationsOverGF2 {
71    fn validate(
72        num_variables: usize,
73        equations: &[Vec<Vec<usize>>],
74    ) -> Result<(), crate::registry::ConstructionError> {
75        for (eq_idx, equation) in equations.iter().enumerate() {
76            for (mono_idx, monomial) in equation.iter().enumerate() {
77                // Check variable indices are in range
78                for &var in monomial {
79                    if var >= num_variables {
80                        return Err(format!(
81                            "Variable index {var} in equation {eq_idx}, monomial {mono_idx} \
82                             is out of range (num_variables = {num_variables})"
83                        )
84                        .into());
85                    }
86                }
87                // Check monomial is sorted and has no duplicates
88                for w in monomial.windows(2) {
89                    if w[0] >= w[1] {
90                        return Err(format!(
91                            "Monomial {mono_idx} in equation {eq_idx} is not strictly sorted: \
92                             found {} >= {}",
93                            w[0], w[1]
94                        )
95                        .into());
96                    }
97                }
98            }
99        }
100        Ok(())
101    }
102
103    /// Create a new `AlgebraicEquationsOverGF2` instance.
104    ///
105    /// Returns an error if any variable index is out of range or any monomial
106    /// is not strictly sorted.
107    pub fn new(
108        num_variables: usize,
109        equations: Vec<Vec<Vec<usize>>>,
110    ) -> Result<Self, crate::registry::ConstructionError> {
111        Self::validate(num_variables, &equations)?;
112        Ok(Self {
113            num_variables,
114            equations,
115        })
116    }
117
118    /// Get the number of variables.
119    pub fn num_variables(&self) -> usize {
120        self.num_variables
121    }
122
123    /// Get the number of equations.
124    pub fn num_equations(&self) -> usize {
125        self.equations.len()
126    }
127
128    /// Get the equations.
129    pub fn equations(&self) -> &[Vec<Vec<usize>>] {
130        &self.equations
131    }
132
133    /// Evaluate a single monomial given a binary assignment.
134    ///
135    /// An empty monomial is the constant 1.
136    /// A non-empty monomial is the product (AND) of the indicated variables.
137    fn evaluate_monomial(monomial: &[usize], assignment: &[bool]) -> usize {
138        if monomial.is_empty() {
139            return 1;
140        }
141        for &var in monomial {
142            if !assignment[var] {
143                return 0;
144            }
145        }
146        1
147    }
148
149    /// Evaluate a single equation (polynomial) given a binary assignment.
150    ///
151    /// Returns true if the polynomial evaluates to 0 (mod 2).
152    fn evaluate_equation(equation: &[Vec<usize>], assignment: &[bool]) -> bool {
153        let sum: usize = equation
154            .iter()
155            .map(|mono| Self::evaluate_monomial(mono, assignment))
156            .sum();
157        sum.is_multiple_of(2)
158    }
159}
160
161#[derive(Deserialize)]
162struct AlgebraicEquationsOverGF2Data {
163    num_variables: usize,
164    equations: Vec<Vec<Vec<usize>>>,
165}
166
167impl<'de> Deserialize<'de> for AlgebraicEquationsOverGF2 {
168    fn deserialize<D>(deserializer: D) -> Result<Self, D::Error>
169    where
170        D: Deserializer<'de>,
171    {
172        let data = AlgebraicEquationsOverGF2Data::deserialize(deserializer)?;
173        Self::new(data.num_variables, data.equations).map_err(D::Error::custom)
174    }
175}
176
177impl Problem for AlgebraicEquationsOverGF2 {
178    const NAME: &'static str = "AlgebraicEquationsOverGF2";
179    type Solution = Vec<bool>;
180    type Value = Or;
181
182    crate::problem_parameters![
183        ("num_equations", num_equations),
184        ("num_variables", num_variables),
185    ];
186
187    fn variant() -> Vec<(&'static str, &'static str)> {
188        crate::variant_params![]
189    }
190
191    fn evaluate(&self, config: &Self::Solution) -> Result<Or, crate::traits::EvaluationError> {
192        if config.len() != self.num_variables {
193            return Err(crate::traits::EvaluationError::InvalidConfiguration(
194                "assignment length does not match the equation variables".into(),
195            ));
196        }
197        Ok({
198            Or(self
199                .equations
200                .iter()
201                .all(|eq| Self::evaluate_equation(eq, config)))
202        })
203    }
204}
205
206impl crate::solvers::BruteForceProblem for AlgebraicEquationsOverGF2 {
207    fn dimensions(&self) -> Vec<usize> {
208        vec![2; self.num_variables]
209    }
210}
211
212crate::declare_variants! {
213    default AlgebraicEquationsOverGF2 => "2^(0.6943 * num_variables)",
214}
215
216crate::register_brute_force! {
217    AlgebraicEquationsOverGF2 decode |_, indices: Vec<usize>| crate::config::config_to_bits(&indices),
218}
219
220#[cfg(feature = "example-db")]
221pub(crate) fn canonical_model_example_specs() -> Vec<crate::example_db::specs::ModelExampleSpec> {
222    vec![crate::example_db::specs::ModelExampleSpec {
223        id: "algebraic_equations_over_gf2",
224        instance: Box::new(
225            AlgebraicEquationsOverGF2::new(
226                3,
227                vec![
228                    // x0*x1 + x2 = 0
229                    vec![vec![0, 1], vec![2]],
230                    // x1*x2 + x0 + 1 = 0
231                    vec![vec![1, 2], vec![0], vec![]],
232                    // x0 + x1 + x2 + 1 = 0
233                    vec![vec![0], vec![1], vec![2], vec![]],
234                ],
235            )
236            .unwrap(),
237        ),
238        // config [1,0,0]: eq1: 0*0+0=0 ✓, eq2: 0*0+1+1=0 ✓, eq3: 1+0+0+1=0 ✓
239        optimal_config: serde_json::json!(vec![true, false, false]),
240        optimal_value: serde_json::json!(true),
241    }]
242}
243
244#[cfg(test)]
245#[path = "../../unit_tests/models/algebraic/algebraic_equations_over_gf2.rs"]
246mod tests;
problemreductions/models/algebraic/algebraic_equations_over_gf2.rs

problemreductions/models/algebraic/
algebraic_equations_over_gf2.rs
