[Rule] X3C to ALGEBRAIC EQUATIONS OVER GF[2]

[isPANN]

Source: X3C
Target: ALGEBRAIC EQUATIONS OVER GF[2]
Motivation: This is the original reduction used by Fraenkel and Yesha (1977) to prove NP-completeness of solving polynomial equations over GF(2). The reduction encodes the exact covering constraints of X3C as polynomial equations: set selection variables are binary (naturally GF(2)), and the requirement that each element is covered exactly once becomes a system of polynomial equations. The key insight is that "exactly one" constraints over {0,1} can be expressed as polynomial identities in GF(2) arithmetic.

Reference: Garey & Johnson, Computers and Intractability, Appendix A7.2, p.251

GJ Source Entry

[AN9] ALGEBRAIC EQUATIONS OVER GF[2]
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 E {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].

Reduction Algorithm

Summary:

Given an X3C instance: universe U = {u_1, ..., u_{3q}} and collection C = {C_1, ..., C_n} where each C_j ⊆ U with |C_j| = 3. Question: is there a sub-collection of exactly q sets that partitions U?

Construct a system of polynomial equations over GF(2) with variables x_1, ..., x_n (one per set C_j):

1. Covering constraints (one per element): For each element u_i ∈ U, let S_i = {j : u_i ∈ C_j} be the indices of sets containing u_i. We need exactly one set covering u_i. Over GF(2), "exactly one of {x_j : j ∈ S_i} is 1" can be encoded as:

   • Linear part: Σ_{j ∈ S_i} x_j + 1 = 0 (mod 2). This forces an odd number of selected sets to cover u_i. (Note: over GF(2), addition is XOR, so Σ x_j = 1 means an odd number are selected.)
   • Pairwise exclusion: For each pair j, k ∈ S_i with j < k, add the equation x_j * x_k = 0. This forbids selecting two sets that both cover u_i.

   Together, these ensure exactly one set covers each element: the linear constraint forces at least one (odd number), and the pairwise products forbid two or more.

2. Cardinality constraint (optional): The constraint Σ x_j = q (select exactly q sets) is implicitly enforced: if every element is covered exactly once and there are 3q elements with 3 elements per set, exactly q sets must be selected.

Correctness: X3C has a solution iff the constructed system of polynomial equations over GF(2) has a solution. If an exact cover {C_{j_1}, ..., C_{j_q}} exists, setting x_{j_k} = 1 and all others to 0 satisfies every equation. Conversely, if (x_1, ..., x_n) satisfies all equations, the selected sets form an exact cover.

Size Overhead

Symbols:

• n = |C| = number of sets (num_sets of source X3C instance)
• 3q = |U| = number of elements (universe_size)
• d = maximum number of sets containing any single element

Target metric (code name)	Polynomial (using symbols above)
num_variables	num_sets (= n)
num_equations	universe_size + O(universe_size * d^2) (3q linear + pairwise product equations)

Derivation: One variable per set in C (n variables). One linear equation per element (3q equations). For each element, at most C(d,2) pairwise product equations where d is the max number of sets containing that element. Total equations are O(3q + 3q * d^2/2). In the worst case d = O(n), giving O(n^2) equations, but typically d is small.

Validation Method

• Closed-loop test: construct an X3C instance, reduce to AlgebraicEquationsOverGF2, solve with BruteForce (enumerate all 2^n assignments), verify that satisfiability of the polynomial system matches existence of an exact cover.
• Correctness check: for a YES instance, verify the satisfying assignment corresponds to a valid exact cover (each element covered exactly once, exactly q sets selected).
• Edge cases: test with no solution (overlapping sets that prevent exact cover); test with trivial instance (q = 1, single 3-element set = universe).

Example

Source instance (X3C):
Universe U = {1, 2, 3, 4, 5, 6} (q = 2, so 3q = 6).
Collection C = {C_1, C_2, C_3} where:

• C_1 = {1, 2, 3}
• C_2 = {4, 5, 6}
• C_3 = {1, 4, 5}

Exact cover: {C_1, C_2} covers all elements exactly once.

Constructed AlgebraicEquationsOverGF2 instance:
Variables: x_1, x_2, x_3 (one per set).

Covering constraints:

• Element 1 (in C_1, C_3): x_1 + x_3 + 1 = 0; x_1 * x_3 = 0
• Element 2 (in C_1 only): x_1 + 1 = 0
• Element 3 (in C_1 only): x_1 + 1 = 0
• Element 4 (in C_2, C_3): x_2 + x_3 + 1 = 0; x_2 * x_3 = 0
• Element 5 (in C_2, C_3): x_2 + x_3 + 1 = 0; x_2 * x_3 = 0
• Element 6 (in C_2 only): x_2 + 1 = 0

After deduplication, the system is:

1. x_1 + x_3 + 1 = 0 (element 1)
2. x_1 * x_3 = 0 (element 1)
3. x_1 + 1 = 0 (elements 2, 3)
4. x_2 + x_3 + 1 = 0 (elements 4, 5)
5. x_2 * x_3 = 0 (elements 4, 5)
6. x_2 + 1 = 0 (element 6)

Verification with (x_1, x_2, x_3) = (1, 1, 0):

1. 1 + 0 + 1 = 0 (mod 2) -- satisfied
2. 1 * 0 = 0 -- satisfied
3. 1 + 1 = 0 (mod 2) -- satisfied
4. 1 + 0 + 1 = 0 (mod 2) -- satisfied
5. 1 * 0 = 0 -- satisfied
6. 1 + 1 = 0 (mod 2) -- satisfied

All equations satisfied. This corresponds to selecting {C_1, C_2}, which is indeed an exact cover.

References

• [Fraenkel and Yesha, 1977]: [Fraenkel1977] A. S. Fraenkel and Y. Yesha (1977). "Complexity of problems in games, graphs, and algebraic equations".
• [Valiant, 1977c]: [Valiant1977c] Leslie G. Valiant (1977). "private communication".

[GiggleLiu]

Implemented in PR #999.