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

problemreductions/models/algebraic/
algebraic_equations_over_gf2.rs
