= Solution
The problem belongs to <NP>: an assignment in $\mathbb F_2^n$ is a polynomial-length <certificate in computational complexity>, and substitution verifies every equation in polynomial time.
For <NP-hardness>, reduce the <Circuit satisfiability problem>. Introduce one variable in $\mathbb F_2$ for every wire of a <Boolean circuit>. A <logical negation> gate $w=\neg u$ is enforced by $w=1-u$, and a <logical conjunction> gate $w=u\wedge v$ is enforced by $w=uv$. For a <logical disjunction> gate use the suggested quadratic equation
$$
(1-u)(1-v)=1-w,
$$
which is equivalent to $w=u\vee v$ for bits $u,v,w$. Add the linear equation $w_{\rm out}=1$ for the designated output wire.
The construction introduces one variable and one equation per wire or gate, so it is a <polynomial-time many-one reduction>. A satisfying circuit input extends uniquely through its gates to a solution of the equations, and any solution gives a consistent accepting circuit computation. Since circuit satisfiability is NP-complete, <quadratic-equation satisfiability over F2> is therefore
$$
\boxed{\mathbf{NP}\text{-complete}.}
$$
Back to article page
