[Model] AlgebraicEquationsOverGF2

[isPANN]

Motivation

ALGEBRAIC EQUATIONS OVER GF[2] (P228) from Garey & Johnson, A7 AN9. A classical NP-complete problem useful for reductions. Fundamental in coding theory, cryptography (Groebner basis attacks on AES), and algebraic complexity theory. Serves as a target for the X3C reduction (R172) established by Fraenkel and Yesha (1979). Remains NP-complete even when restricted to degree-2 polynomials (Valiant, 1979).

Associated rules:

• [Rule] X3C to ALGEBRAIC EQUATIONS OVER GF[2] #859: ExactCoverBy3Sets → AlgebraicEquationsOverGF2 (classical NP-completeness proof)

Definition

Name: AlgebraicEquationsOverGF2
Reference: Garey & Johnson, Computers and Intractability, A7 AN9

Mathematical definition:

INSTANCE: Polynomials P_i(x_1, x_2, . . . , x_n), 1 ≤ i ≤ m, over GF[2], i.e., each polynomial is a sum of terms, where each term is either the integer 1 or a product of distinct x_i.
QUESTION: Do there exist u_1, u_2, . . . , u_n ∈ {0,1} such that, for 1 ≤ i ≤ m, P_i(u_1, u_2, . . . , u_n) = 0, where arithmetic operations are as defined in GF[2], with 1+1 = 0 and 1·1 = 1?

Variables

• Count: n binary variables (x_1, ..., x_n)
• Per-variable domain: {0, 1} (elements of GF(2))
• Meaning: x_j = u_j is the assignment to variable j. Since variables are over GF(2), all polynomials are multilinear (x_j^2 = x_j). The system is satisfiable iff there exists an assignment (u_1, ..., u_n) ∈ {0,1}^n such that every polynomial evaluates to 0 under GF(2) arithmetic.

Schema (data type)

Type name: AlgebraicEquationsOverGF2
Variants: none (polynomials are always multilinear over GF(2); no type parameters)

Field	Type	Description
num_variables	usize	Number of variables n
equations	Vec<Vec<Vec<usize>>>	Each equation is a list of monomials; each monomial is a sorted list of variable indices (empty = constant 1)

Notes:

• This is a feasibility (decision) problem: Value = Or.
• Key getter methods: num_variables() (= n), num_equations() (= m).
• Each equation represents a polynomial P_i = 0. A monomial is a product of distinct variables identified by index. The empty monomial [] represents the constant 1. Addition is XOR (mod 2). For example, x_1 * x_2 + x_3 + 1 = 0 is represented as [[0, 1], [2], []].

Complexity

• Decision complexity: NP-complete (Fraenkel and Yesha, 1979; transformation from X3C). Remains NP-complete even when restricted to degree-2 (quadratic) polynomials (Valiant, 1979). Linear systems (degree 1) are solvable in polynomial time via Gaussian elimination over GF(2).
• Best known exact algorithm (degree-2): O*(2^{0.6943n}) via improved parity-counting techniques (Dinur, SODA 2021), building on Bjorklund, Kaski & Williams (ICALP 2019, O*(2^{0.804n})) and Lokshtanov, Paturi, Tamaki, Williams & Yu (SODA 2017, O*(2^{0.876n})).
• General degree-d: O*(2^{(1 - 1/(5d))n}) (Lokshtanov et al., SODA 2017).
• Concrete complexity expression: "2^(0.6943 * num_variables)" (for declare_variants!; degree-2 bound, the most common case)
• References:
  • A.S. Fraenkel, Y. Yesha (1979). "Complexity of problems in games, graphs and algebraic equations." Discrete Applied Mathematics, 1(1-2):15-30.
  • I. Dinur (2021). "Improved Algorithms for Solving Polynomial Systems over GF(2) by Multiple Parity-Counting." SODA 2021.
  • A. Bjorklund, P. Kaski, R. Williams (2019). "Solving Systems of Polynomial Equations over GF(2) by a Parity-Counting Self-Reduction." ICALP 2019.
  • D. Lokshtanov, R. Paturi, S. Tamaki, R. Williams, H. Yu (2017). "Beating Brute Force for Systems of Polynomial Equations over Finite Fields." SODA 2017.

Extra Remark

Full book text:

INSTANCE: Polynomials P_i(x_1, x_2, . . . , x_n), 1 ≤ i ≤ m, over GF[2], i.e., each polynomial is a sum of terms, where each term is either the integer 1 or a product of distinct x_i.
QUESTION: Do there exist u_1, u_2, . . . , u_n ∈ {0,1} such that, for 1 ≤ i ≤ m, P_i(u_1, u_2, . . . , u_n) = 0, where arithmetic operations are as defined in GF[2], with 1+1 = 0 and 1·1 = 1?

Reference: [Fraenkel and Yesha, 1977]. Transformation from X3C.
Comment: Remains NP-complete even if none of the polynomials has a term involving more than two variables [Valiant, 1977c]. Easily solved in polynomial time if no term involves more than one variable or if there is just one polynomial. Variant in which the u_j are allowed to range over the algebraic closure of GF[2] is NP-hard, even if no term involves more than two variables [Fraenkel and Yesha, 1977].

How to solve

• It can be solved by (existing) bruteforce. (Enumerate all 2^n assignments; check if every polynomial evaluates to 0 mod 2.)
• It can be solved by reducing to integer programming. (Each polynomial equation P_i = 0 over GF(2) can be linearized by introducing auxiliary variables for each product term, then requiring the XOR of all terms to be 0, expressible as a linear constraint modulo 2 embedded in ILP. Companion rule issue to be filed separately.)
• Other: Groebner basis methods; parity-counting algorithms (Lokshtanov et al. 2017, Bjorklund et al. 2019).

Example Instance

Input:
n = 3 variables: x_1, x_2, x_3
m = 3 quadratic equations over GF(2):

• P_1: x_1 · x_2 + x_3 = 0
• P_2: x_2 · x_3 + x_1 + 1 = 0
• P_3: x_1 + x_2 + x_3 + 1 = 0

Represented as:

equations = [
  [[0, 1], [2]],             // x1*x2 + x3
  [[1, 2], [0], []],         // x2*x3 + x1 + 1
  [[0], [1], [2], []],       // x1 + x2 + x3 + 1
]

Feasible assignment: (x_1, x_2, x_3) = (1, 0, 0):

• P_1: 1·0 + 0 = 0 (mod 2) ✓
• P_2: 0·0 + 1 + 1 = 0 (mod 2) ✓
• P_3: 1 + 0 + 0 + 1 = 0 (mod 2) ✓

Answer: YES — this is the unique satisfying assignment (1 out of 8 possible).

Negative example:
Replace P_2 with P_2': x_1 · x_2 + x_3 + 1 = 0. Now P_1 and P_2' are contradictory: P_1 requires x_1·x_2 + x_3 = 0 while P_2' requires x_1·x_2 + x_3 + 1 = 0, which means 0 = 1 in GF(2) — impossible regardless of the variable assignment. Answer: NO.

Python validation script

# Positive example
satisfying = []
for x1 in range(2):
    for x2 in range(2):
        for x3 in range(2):
            p1 = (x1*x2 + x3) % 2
            p2 = (x2*x3 + x1 + 1) % 2
            p3 = (x1 + x2 + x3 + 1) % 2
            if p1 == 0 and p2 == 0 and p3 == 0:
                satisfying.append((x1, x2, x3))
assert satisfying == [(1, 0, 0)]
print(f"Positive: {len(satisfying)} satisfying assignment(s): {satisfying}")

# Negative example (P1 and P2' contradict)
satisfying_neg = []
for x1 in range(2):
    for x2 in range(2):
        for x3 in range(2):
            p1 = (x1*x2 + x3) % 2
            p2p = (x1*x2 + x3 + 1) % 2  # contradicts P1
            p3 = (x1 + x2 + x3 + 1) % 2
            if p1 == 0 and p2p == 0 and p3 == 0:
                satisfying_neg.append((x1, x2, x3))
assert len(satisfying_neg) == 0
print("Negative: 0 satisfying assignments (correct)")

[isPANN]

Issue Quality Check — Model

Check	Result	Details
Usefulness	✅ Pass	Novel problem not yet in the reduction graph; concrete X3C reduction planned
Non-trivial	✅ Pass	Distinct feasibility constraints (polynomial system over GF(2)) from all existing problems
Correctness	⚠️ Warn	Complexity claims verified; minor reference year discrepancy (1979 publication cited as 1977)
Well-written	❌ Fail	Missing ILP companion issue link; missing concrete complexity expression; title/name inconsistency

Overall: 2 passed, 1 warning, 1 failed

---

Usefulness

Pass. The problem AlgebraicEquationsOverGF2 does not exist in the codebase. The issue mentions a concrete planned reduction from ExactCoverBy3Sets (X3C), which is already implemented. The problem has clear applications in coding theory, cryptography, and algebraic complexity theory. This adds genuine value to the reduction graph.

Non-trivial

Pass. This problem has a genuinely distinct structure from all existing problems. The feasibility constraint is satisfiability of a system of multilinear polynomials under GF(2) arithmetic (XOR addition, AND multiplication). No existing problem in the codebase captures this structure. The closest existing problems (QuadraticDiophantineEquations, FeasibleBasisExtension) operate over different domains and have different constraint structures.

Correctness

Warn — minor reference year discrepancy, otherwise verified.

• Fraenkel and Yesha: The issue cites "Fraenkel and Yesha (1977)". The published paper is: Fraenkel, A. S. & Yesha, Y., "Complexity of problems in games, graphs and algebraic equations," Discrete Applied Mathematics, 1(1-2):15–30, 1979. Garey & Johnson cite it as "1977" (likely a technical report date). The content claim (NP-completeness via X3C reduction) is correct.
• Valiant (1977c): The claim that the problem remains NP-complete even when no polynomial has a term involving more than two variables is attributed to Valiant. This corresponds to Valiant's "Completeness classes in algebra" (STOC 1979, also likely a 1977 technical report). The claim is consistent with established results.
• Dinur (2021): The claim of O*(2^{0.6943n}) for degree-2 systems is verified. This is from: Dinur, I., "Improved Algorithms for Solving Polynomial Systems over GF(2) by Multiple Parity-Counting," SODA 2021. Confirmed.
• Bjorklund, Kaski & Williams (ICALP 2019): The claim of O*(2^{0.804n}) is verified. Confirmed from the ICALP 2019 proceedings.
• Lokshtanov, Paturi, Tamaki, Williams & Yu (SODA 2017): The claim of O*(2^{0.876n}) and O*(2^{(1-1/(5d))n}) for general degree-d is verified. Confirmed.
• Example verification: The example instance with (x_1, x_2, x_3) = (1, 0, 0) was verified by hand. All three equations evaluate to 0 mod 2. Only 1 out of 8 possible assignments is satisfying, providing a meaningful mix of satisfying/non-satisfying configurations.

Well-written

Fail — 3 issues found.

1. Missing ILP companion issue link (Fail): The "How to solve" section checks the ILP box and describes how to linearize GF(2) polynomial equations for ILP, but there is no "Reduction Rule Crossref" section linking a companion [Rule] AlgebraicEquationsOverGF2 to ILP issue. Per project conventions, if direct ILP solving is claimed, a companion rule issue must be linked.

2. Missing concrete complexity expression (Fail): The Complexity section provides prose descriptions of multiple algorithms but does not include a single concrete complexity expression in the required format (e.g., 2^{0.6943 * num_variables} for the degree-2 case). The declare_variants! macro needs a concrete expression string — the issue should specify which bound applies to the general (unrestricted-degree) case being implemented and express it in terms of problem parameters.

3. Title/name inconsistency (Warn): The issue title uses AlgebraicEquationsOverGf[2] (lowercase 'f', brackets around 2), while the body uses AlgebraicEquationsOverGF2 (uppercase 'F', no brackets). The body version AlgebraicEquationsOverGF2 is the correct Rust identifier form; the title should match.

Recommendations

• Add a "Reduction Rule Crossref" section linking a [Rule] AlgebraicEquationsOverGF2 to ILP issue, or uncheck the ILP box if no direct ILP rule is planned (the problem can still be solved via ILP through composite reduction paths).
• Add a concrete complexity expression. Since the problem allows arbitrary-degree polynomials, the general Lokshtanov et al. bound 2^{(1 - 1/(5*max_degree)) * num_variables} could be used, but max_degree would need to be a getter on the problem type. Alternatively, restrict the declared complexity to degree-2 (the most common and well-studied case) and use 2^{0.6943 * num_variables}.
• Fix the title to match the body: [Model] AlgebraicEquationsOverGF2.

[isPANN]

Fix-issue changelog

• Title: Fixed AlgebraicEquationsOverGf[2] → AlgebraicEquationsOverGF2 (valid Rust identifier).
• Associated rules: Linked rule issue [Rule] X3C to ALGEBRAIC EQUATIONS OVER GF[2] #859 (X3C → AlgebraicEquationsOverGF2).
• Complexity: Added concrete expression "2^(0.6943 * num_variables)" for declare_variants! (degree-2 Dinur 2021 bound). Fixed Fraenkel-Yesha reference year from 1977 (tech report) to 1979 (published).
• Schema notes: Added getter methods (num_variables(), num_equations()).
• ILP: Added companion rule note.
• Example: Added negative example (contradictory equations making system unsatisfiable regardless of assignment).
• Added Python validation script verifying both positive (1/8 satisfying) and negative (0/8) cases.

Applied by /fix-issue.