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