Hardness of a class of quadratics

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

Solved by user5038 (10,393 )
Jun 09, 2022 at 18:30