# On the hardness of constraint satisfaction

I am interested in the hardness of the following question.

Suppose we have a vector of $$n$$ optimization variables $$\mathbf{x} = \langle x_1, . . ., x_n\rangle$$ and $$m$$ vectors $$\mathbf{v}_1, . . .,\mathbf{v}_m$$ with each $$\mathbf{v}_j \in \{-1,1\}$$.

Our objective is to maximize the number of nonnegative dot products between $$\mathbf{x}$$ and each $$\mathbf{v}_j$$, where each $$0\leq x_i\leq 1$$.

That is

$$\max_{\mathbf{x}}\sum_{j=1}^n\mathbb{I}[\langle \mathbf{x}, \mathbf{v}_j\rangle \geq 0]$$

$$\text{such that} 0\leq x_i \leq 1$$

These constitute linear constraints and I know in general that maximizing the number of satisfied linear constraints is NP, but these constraints differ in two main ways. The first is that none have a bias term, and the second is that each coefficient of the optimization variables is either 1 or -1.

• Doesn't $x = 0$ always maximise the objective? Jan 6, 2020 at 9:23

As pointed out by Antti Röyskö the solution $$\mathbf{x} = 0$$ always maximizes the objective function since $$\sum_{j=1}^n\mathbb{I}[\langle \mathbf{x}, \mathbf{v}_j\rangle \geq 0]$$ corresponds to the number of constraints $$\langle \mathbf{x}, \mathbf{v}_j\rangle \geq 0$$ which are satsificed, and $$\mathbf{x}$$ satifies all constraints.
However, the problem becomes much more interesting if we dont allow degenerate solutions. In fact, by removing $$\mathbf{x} = 0$$, the problem goes from having a closed form solution, to being NP-hard. It takes a bit of work, but you can actually reduce any integer feasibility program down to your problem.