AN8 is Quadratic Diophantine Equations.

**The problem: **Algebraic Equations over GF[2]. This is problem AN9 in the appendix.

**The description: **Given a set P of m polynomials over n variables (x_{1} through x_{n}) where each polynomial is the sum of terms that is either 1 or the product of distinct x_{i}, can we find a value u_{i} for each x_{i} in the range {0,1} that make each polynomial 0, if we define 1+1=0, and 1*1 = 1?

**Example: **It helps to think of GF[2] as a boolean logic world, where + is XOR and * is AND. So, suppose we have three variables, and the polynomials:

- P
_{1}= 1 + x_{1}x_{2}+ x_{2}x_{3} - P
_{2}= x_{1}+ x_{1}x_{2}x_{3}

..Then setting x_{1}=0, x_{2}=1, x_{3}=1 makes both polynomials 0.

**Reduction**: G&J say that Fraenkel and Yesha use X3C, but the paper I found uses 3SAT. We’re given an equation that has n variables and m clauses. The variables of our polynomials will be the same variables in the 3SAT instance. For each clause, we build a polynomial by:

- Replacing a negated literal (~x) with the equation 1 + x. (Remember, + means XOR in this system)
- Replacing an OR clause (A ∨ B) with the equation A+ B +A*B
- Xoring the whole above thing with 1.

Notice that the first replacement makes ~x have the opposite truth value of x, the second replacement rule is logically equivalent to A∨B, and the third part makes the polynomial 0 if and only if the clause evaluated to 1. So the polynomial is 0 if and only if the clause is satisfiable. So all polynomials are 0 if and only if the all clauses are satisfiable.

**Difficulty: **5. This is easy to follow. It’s a little tricky to make students come up with the equivalence rules above, but I think if you can explain it right, it’s not that bad.