3
$\begingroup$

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.

$\endgroup$
5
$\begingroup$

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.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – user2566092 Sep 13 '15 at 18:14

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.