A special case of the boolean multivariate quadratic polynomial problem

Question

It's well known that in the general case, the boolean MQ problem:

given $(f_1, \ldots, f_n) \in \mathbb{F}_2[x_1, \ldots, x_m]$ with $\deg(f_i) = 2$, can we find a solution $\vec{y}: f_i(\vec{y}) = 0$,

is NP-hard. I was wondering if there was an efficient algorithm for the special case in which each $f_i$ is the product of linear functions?

Answer 1

This case is still NP-hard. Suppose we have an instance of 3-SAT:

$F=C_1\wedge\ldots\wedge C_n; C_i=L_{i,1}\vee L_{i,2}\vee L_{i,3}$,

where each literal $L_{i,j}$ is either $V$ or $\neg V$ for some boolean variable $V\in Var$. We can translate this into an equivalent system of equations $f_{i,j}=0$ for $i=1,\dots,n$ and $1\le j\le 4$, where each $f_{i,j}$ is a product of two linear factors, as follows.

Introduce a variable $V'$ for each $V\in Var$, variables $c_i,d_i$ for each clause $C_i$, and an auxiliary variable $z$. For all $i$ and each $1\le j\le 3$, let $t_{i,j}$ be $V'$ if $L_{i,j}=V$, and $(1-V')$ if $L_{i,j}=\neg V$. Then the fact that clause $C_i$ is supposed to be satisfied by a valuation of $Var$ can be split into the conditions:

• $(1-c_i)z = (1-c_i)(1-z) = 0$, forcing the value of $c_i$ to be $1$;
• $(c_i-d_i)(c_i-t_{i,1}) = 0$, forcing $c_i$ to equal $d_i$ or $t_{i,1}$; and
• $(d_i-t_{i,2})(d_i-t_{i,3})=0$, forcing $d_i$ to equal $t_{i,2}$ or $t_{i,3}$.

Together these force at least one of the $t_{i,j}$ to be $1$, corresponding to one of the $L_{i,j}$ being true. Combining these for all $i$ gives a system of equations equivalent to $F$.