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.


1 Answer 1


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$


$\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$.

  • $\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, 2014 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, 2014 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$ Nov 25, 2014 at 20:52
  • $\begingroup$ Very nice, and almost annoyingly simple :) $\endgroup$
    – Shaull
    Nov 26, 2014 at 6:10

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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