<p>Yes, it is NP-hard.  You can express <span class="math-container">$x_3=\neg(x_1 \land x_2)$</span> using these constraints, so you can express an arbitrary logical circuit (since NAND is universal), so you can reduce from satisfiability of CircuitSAT.</p>
<p>First, add the inequalities <span class="math-container">$x_i^2 \le x_i$</span> for all <span class="math-container">$i$</span>.  This ensures each <span class="math-container">$x_i$</span> is 0 or 1.</p>
<p>Second, we'll ensure that all <span class="math-container">$\alpha_i$</span> are 0 or 1 as well, by introducing fresh <span class="math-container">$x$</span>-variables, one per <span class="math-container">$\alpha_i$</span>: e.g., for each <span class="math-container">$i$</span>, introduce a fresh <span class="math-container">$x$</span>-variable, call it <span class="math-container">$t$</span>, and add <span class="math-container">$t=\alpha_i$</span>, <span class="math-container">$t^2 \le t$</span>.  (Here &quot;<span class="math-container">$t$</span>&quot; is short-hand for <span class="math-container">$x_k$</span> where <span class="math-container">$k$</span> is some unique index that is specific to <span class="math-container">$i$</span> and different from all other existing <span class="math-container">$x$</span>-variables.)</p>
<p>How to express <span class="math-container">$x_3 = x_1 \land x_2$</span>: create fresh <span class="math-container">$\alpha$</span>-variables that I'll call <span class="math-container">$\alpha_{11},\alpha_{10},\alpha_{01},\alpha_{00}$</span> (with unique indices). Add the equalities <span class="math-container">$x_1 = \alpha_{11} + \alpha_{10}$</span>, <span class="math-container">$x_2 = \alpha_{01} + \alpha_{00}$</span>, <span class="math-container">$x_3=\alpha_{10}+\alpha_{01}+\alpha_{00}$</span>.  Also, for each <span class="math-container">$i,j \in \{00,01,10,11\}$</span> with <span class="math-container">$i\ne j$</span>, add the constraint <span class="math-container">$\alpha_i + \alpha_j \le 1$</span>.  Also, add the constraint <span class="math-container">$1 \le \alpha_{11} + \alpha_{10} + \alpha_{01} + \alpha_{00}$</span>.</p>
<p>Notice that you can enforce <span class="math-container">$\alpha_i + \alpha_j \le 1$</span> by adding fresh <span class="math-container">$x$</span>-variables, call them <span class="math-container">$u,v$</span>, along with <span class="math-container">$u=\alpha_i + \alpha_j$</span>, <span class="math-container">$v=3$</span>, and <span class="math-container">$u^2 \le v$</span>.</p>
<p>Similarly, you can enforce <span class="math-container">$1 \le \alpha_{11} + \alpha_{10} + \alpha_{01} + \alpha_{00}$</span> by adding fresh <span class="math-container">$x$</span>-variables, call them <span class="math-container">$r,s$</span>, along with <span class="math-container">$r=1$</span> and <span class="math-container">$s=\alpha_{11} + \alpha_{10} + \alpha_{01} + \alpha_{00}$</span> and <span class="math-container">$r^2 \le s$</span>.</p>
<p>Why does this work?  The intuition is that the constraints ensure that <span class="math-container">$\alpha_{11}$</span> will be true iff <span class="math-container">$x_1=1$</span> and <span class="math-container">$x_2=1$</span>, <span class="math-container">$\alpha_{10}$</span> will be true iff <span class="math-container">$x_1=1$</span> and <span class="math-container">$x_2=0$</span>, and so on.  The rest follows.</p>
<p>I am assuming you can have arbitrarily many equalities per <span class="math-container">$x_i$</span>.  If that's not allowed, then it's possible to deal with that, too.  If we want two equalities for <span class="math-container">$x_i$</span>, we can introduce a fresh <span class="math-container">$x$</span>-variable <span class="math-container">$t$</span>, with one equality for <span class="math-container">$x_i$</span> and one equality for <span class="math-container">$t$</span>, and then add inequalities <span class="math-container">$x_i^2 \le t$</span> and <span class="math-container">$t^2 \le x_i$</span> (to force <span class="math-container">$x_i=t$</span>).</p>

CC BY-SA 4.0
2022-06-09T23:02:29.340Z
@Rodrigo, if that is limited, I encourage you to edit your question to specify more precisely what is allowed and what is not.  In any case, I've edited my answer to deal with that case as well.  See the last paragraph of the edited answer.
D.W.
CC BY-SA 4.0
2022-06-09T18:30:13.003Z
2022-06-09T23:04:30.507Z
2022-06-09T23:04:30.507Z
D.W.
<p>I have a system of inequalities of the form <span class="math-container">$x_i^2 \le x_j$</span> with <span class="math-container">$x_i = a_i + \sum_j \alpha_j b_{i,j}$</span>, the variables are <span class="math-container">$x_i,\alpha_i$</span>, the values <span class="math-container">$a_i,  b_{i,j} \ge 0$</span> are known and all <span class="math-container">$x_i, a_i, \alpha_j, b_{i,j} \in \mathbb{N}$</span>.</p>
<p>Is this problem NP-hard?</p>

<np-hardness>
Hardness of a class of quadratics
user1868607
# Hardness of a class of quadratics

(Asked by: username_0 on 2022-06-09)

I have a system of inequalities of the form $x\_i^2 \le x\_j$ with $x\_i = a\_i + \sum\_j \alpha\_j b\_{i,j}$, the variables are $x\_i,\alpha\_i$, the values $a\_i, b\_{i,j} \ge 0$ are known and all $x\_i, a\_i, \alpha\_j, b\_{i,j} \in \mathbb{N}$.

Is this problem NP-hard?

**Tags:** np-hardness

---

## 1 answers

### Answer by username_1 on 2022-06-09. Score: 5 | Accepted answer

Yes, it is NP-hard. You can express $x\_3=\neg(x\_1 \land x\_2)$ using these constraints, so you can express an arbitrary logical circuit (since NAND is universal), so you can reduce from satisfiability of CircuitSAT.

First, add the inequalities $x\_i^2 \le x\_i$ for all $i$. This ensures each $x\_i$ is 0 or 1.

Second, we'll ensure that all $\alpha\_i$ are 0 or 1 as well, by introducing fresh $x$-variables, one per $\alpha\_i$: e.g., for each $i$, introduce a fresh $x$-variable, call it $t$, and add $t=\alpha\_i$, $t^2 \le t$. (Here "$t$" is short-hand for $x\_k$ where $k$ is some unique index that is specific to $i$ and different from all other existing $x$-variables.)

How to express $x\_3 = x\_1 \land x\_2$: create fresh $\alpha$-variables that I'll call $\alpha\_{11},\alpha\_{10},\alpha\_{01},\alpha\_{00}$ (with unique indices). Add the equalities $x\_1 = \alpha\_{11} + \alpha\_{10}$, $x\_2 = \alpha\_{01} + \alpha\_{00}$, $x\_3=\alpha\_{10}+\alpha\_{01}+\alpha\_{00}$. Also, for each $i,j \in \{00,01,10,11\}$ with $i\ne j$, add the constraint $\alpha\_i + \alpha\_j \le 1$. Also, add the constraint $1 \le \alpha\_{11} + \alpha\_{10} + \alpha\_{01} + \alpha\_{00}$.

Notice that you can enforce $\alpha\_i + \alpha\_j \le 1$ by adding fresh $x$-variables, call them $u,v$, along with $u=\alpha\_i + \alpha\_j$, $v=3$, and $u^2 \le v$.

Similarly, you can enforce $1 \le \alpha\_{11} + \alpha\_{10} + \alpha\_{01} + \alpha\_{00}$ by adding fresh $x$-variables, call them $r,s$, along with $r=1$ and $s=\alpha\_{11} + \alpha\_{10} + \alpha\_{01} + \alpha\_{00}$ and $r^2 \le s$.

Why does this work? The intuition is that the constraints ensure that $\alpha\_{11}$ will be true iff $x\_1=1$ and $x\_2=1$, $\alpha\_{10}$ will be true iff $x\_1=1$ and $x\_2=0$, and so on. The rest follows.

I am assuming you can have arbitrarily many equalities per $x\_i$. If that's not allowed, then it's possible to deal with that, too. If we want two equalities for $x\_i$, we can introduce a fresh $x$-variable $t$, with one equality for $x\_i$ and one equality for $t$, and then add inequalities $x\_i^2 \le t$ and $t^2 \le x\_i$ (to force $x\_i=t$).

> **Comments:**
> **username_1**: @Rodrigo, if that is limited, I encourage you to edit your question to specify more precisely what is allowed and what is not.  In any case, I've edited my answer to deal with that case as well.  See the last paragraph of the edited answer.  

---

