Theoretical Computer Science
np-hardness
Updated Thu, 23 Jun 2022 17:20:36 GMT

Hardness of a class of quadratics


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?




Solution

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 (1)

  • +3 – @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. — Jun 09, 2022 at 23:02