4
$\begingroup$

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?

$\endgroup$
5
$\begingroup$

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$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.