3
$\begingroup$

The PARTITION problem: $\{\{x_1,...,x_n\}: \exists I\subseteq[n], \sum_{i\in I}x_i=\sum_{i\notin I}x_i\}$ is well known to be NP-complete.

My question: does the partition problem remain NP-complete (as a promise-problem) if we are given that $\sum_{i=1}^n x_i=0$?.

A problem that arises in this assumption is that one can always take the empty-set, so we also need to require that $I$ is nontrivial.

Note that for the related SUBSET-SUM problem, it is easy to show that the problem remains NP-complete (reduce from subset-sum of positive numbers by adding the negation of the sum).

My guess is that the problem remains NP-complete, but no proof yet.

$\endgroup$
4
$\begingroup$

No. The problem is trivial, since taking $I$ to be the empty set always results in a solution to the problem.

Yes, it is NP-complete. Note that if there is a solution, that is

$\Sigma_{i\in I} x_i = \Sigma_{i\not\in I} x_i$

then

$\Sigma_{i\in I} x_i - \Sigma_{i\not\in I} x_i = 0$.

Since we have

$\Sigma_{i\in I} x_i + \Sigma_{i\not\in I} x_i = 0$

then $\Sigma_{i\not\in I} x_i = 0$ and $\Sigma_{i\in I} x_i = 0$.

Proof of NP-hardness is by reduction from partition. For a given instance of the partition problem, a multiset $S$ of integers, where $\Sigma_{s\in S}=2N$, create an instance of Partition with 0-SUM, by adding 2 copies of $-N$ to $S$.

Clearly, if the Partition instance has a solution then so does the modified problem, by adding $-N$ to each half of the partition. If the Partition with 0-SUM restriction has a solution, then so does the original Partition problem: since all the integers in the original partition problem are positive, each 0-SUM "half" of the 0-SUM partition must contain one of $-N$, and the rest must sum to $N$.

$\endgroup$
  • $\begingroup$ Yes, I forgot to add that in this case we need to require the sets to be nontrivial, of course. Thanks, I've edited the post. $\endgroup$ – Shaull Nov 25 '14 at 20:02
  • $\begingroup$ I don't see how you got to the last conclusion. For example, if we have the set ${2,-2,4,-4}$ then there is clearly a solution, but no $x_i$ is $0$. $\endgroup$ – Shaull Nov 25 '14 at 20:22
  • 1
    $\begingroup$ My bad, I was wrong. But I think I managed to salvage the answer and provide a NP-completeness proof. $\endgroup$ – Tom van der Zanden Nov 25 '14 at 20:52
  • $\begingroup$ Very nice, and almost annoyingly simple :) $\endgroup$ – Shaull Nov 26 '14 at 6:10

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.