patternMinor
PARTITION with 0-sum assumption
Viewed 0 times
withassumptionpartitionsum
Problem
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.
$\{\{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.
Solution
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$.
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$.
Context
StackExchange Computer Science Q#33518, answer score: 4
Revisions (0)
No revisions yet.