# Is multiple equation 0/1 linear integer programming with bounded integer weights NP-hard?

Suppose we forget about optimizing and just want to find a feasible solution to a set of equations:

$$\sum_i w_{ij} x_i = W_j.$$

Here we are given $w_{ij}$ and $W_j$, and want to solve for $x_i$. Also $x_i$ are restricted to be 0/1 and we're promised that $w_{ij}$ and $W_j$ will be non-negative integer constants and we will have $w_{ij} \leq M$ for some universal constant $M$. The number of variables and equations can be arbitrary.

Is this an NP-complete problem? If we have just one or a universal bounded number of equations then the problem can be solved in polynomial time. Certainly if we can find a solution then we can verify it in polynomial time, so the problem is in NP. I was trying to find a reduction from something like 3-SAT in the general case but to no avail.

This problem is NP-complete, by reduction from 1-in-3 positive 3SAT.

1-in-3 positive 3SAT is a variant of 3SAT, where we require that exactly each clause consists of 3 positive literals (no negation), and to satisfy the formula, exactly one literal in each clause must be true (no more, no less). Thus, each 1-in-3 positive 3SAT instance is a formula

$$\varphi(x_1,\dots,x_n) = \bigwedge_i (x_{c_{i,1}} \sqcup x_{c_{i,2}} \sqcup x_{c_{i,3}}),$$

where $x \sqcup y \sqcup z$ is true iff exactly one of $x,y,z$ is true.

You can immediately convert this to an instance of your problem. In particular, the $i$th clause corresponds to an equation

$$x_{c_{i,1}} + x_{c_{i,2}} + x_{c_{i,3}} = 1.$$

For instance, the clause $(x_3 \sqcup x_5 \sqcup x_6)$ corresponds to the equation $x_3 + x_5 + x_6 = 1$. We get one equation per clause. The equations are simultaneously satisfiable iff the formula $\varphi$ is satisfiable. This completes the reduction.

• Very nice, this confirmed my intuition that it probably was easiest to see with SOMETHING related to SAT. I'll remember 1-in 3 positive SAT now. – user2566092 Sep 13 '15 at 18:14