 Quadratic-equation satisfiability over F2

Quadratic-equation satisfiability over F2 asks whether finitely many polynomials of polynomial degree at most two over the finite field ${\mathbb{F}}_2$ have a common zero. Each unknown therefore takes one of the two truth values zero and one, with addition and multiplication performed modulo two.

A Boolean circuit can be encoded by introducing a Boolean variable for every logic gate output. An AND gate $z=x\wedge y$ becomes $z+xy=0$, while a NOT gate $z=\neg x$ becomes $z+x+1=0$. Forcing the final output to one adds $z_{\mathrm{out}}+1=0$. All these constraints have degree at most two, and an assignment to the logic gate variables solves them exactly when it is a consistent accepting Boolean circuit evaluation.

The construction has polynomial size and reduces the Circuit satisfiability problem to this task. Guessing values and checking the displayed polynomials proves membership in NP, so the problem is NP-complete. This explains why allowing quadratic terms changes the computational picture from a system of linear equations solved by Gaussian elimination.