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

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

<p>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.</p>

<p>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:</p>

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

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

CC BY-SA 3.0
2016-02-01T22:03:11.580Z
2016-02-01T22:03:11.580Z
Klaus Draeger
<p>It's well known that in the general case, the boolean MQ problem:</p>

<p>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$,</p>

<p>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?</p>

<cc.complexity-theory><polynomials>
A special case of the boolean multivariate quadratic polynomial problem
squiggles
# A special case of the boolean multivariate quadratic polynomial problem

(Asked by: username_0 on 2016-02-01)

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?

**Tags:** cc.complexity-theory, polynomials


---

## 1 answers

### Answer by username_1 on 2016-02-01. Score: 5 | Accepted answer

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


---

