# NP-Completeness

Consider the following optimization problem: \begin{align} \text{Min}&&\frac{1}{2}\sum_{(i,j,s,t)\in I}\|x_ix_j-x_sx_t\|\\ s.t.: && Ax=b\\ &&x\geq 0 \end{align} where $I$ is a finite set of indices. It seems that this problem is NP-complete. How can I find a suitable reduction for this?

-
What are $x$, $A$, $b$, and $o$? –  Emil Jeřábek Jul 9 at 12:44
$x$ is the decision variable. $A$ and $b$ are adjacency matrix and right hand side vector, respectively. –  Star Jul 9 at 13:41
Are they real, integer, or something else? –  Emil Jeřábek Jul 9 at 14:01
cross-posted –  Emil Jeřábek Jul 9 at 16:11
Star, if your input is real, then I can't understand your problem as being even computable, let alone in NP. (But from your latest comment it seems you do not follow the usual distinction between NP-complete, which implies NP, and NP-hard, which does not.) After all, we cannot computably decide even whether $Ax=b$, even when $A$ is the identity matrix, if we are dealing with real numbers as input, since equality of reals is not computably decidable. But also, I'm still not entirely clear what your decision problem is exactly, in terms of what is input and what are fixed parameters. –  Joel David Hamkins Jul 9 at 17:15