= Quadratic-equation satisfiability over F2
{title2=$\mathrm{MQ}_{\mathbb F_2}$}
<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\land 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>.
Back to article page
