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$

1 Answer 1

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$
4
  • $\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

This site is temporarily in read-only mode and not accepting new answers.

Not the answer you're looking for? Browse other questions tagged .