Given a set $A=\{a_{1},a_{2},a_{3},\ldots,a_{n}\}$, then construct a set $P=\{p_{1}, p_{2}, p_{3}, \ldots , p_{n}\}$ such that

  1. $|p_{i}|=a_{i}$, and

  2. $\sum_{i = 1,}^{n}p_{i} = 0$.

This problem is NP-complete, which I want to prove.

How do I do it?

I am thinking of a reduction from the subset sum problem. But the problem is that because of the mod.

  • $\begingroup$ What do you mean by "$1.|p_i| = a_i \, 2$"? $\endgroup$ – Yuval Filmus Nov 19 '12 at 7:18
  • $\begingroup$ @YuvalFilmus it actually 2 conditions. 1 and 2. $\endgroup$ – Aakash Anuj Nov 19 '12 at 7:29
  • $\begingroup$ We see that there are two conditions. What does the first condition say? $|p_i|=a_i$? $\endgroup$ – Nejc Nov 19 '12 at 8:10

I'm going to make a few guesses as to what you precisely mean, and if they're correct, we can edit the question so everything is clearer. First I'll define what I think you mean with your problem:

Input: A set of positive integers $A=\{a_{1}, \ldots, a_{n}\}$.
Question: Is there a set of integers $P = \{p_{1}, \ldots, p_{n}\}$ such that for each $i$ the absolute value of $p_{i}$ equals $a_{i}$ (i.e. $|p_{i}| = a_{i}$) and the sum of the elements of $P$ is zero (i.e. $\sum_{i=1}^{n}p_{i} = 0$)?

Clearly what we want to do is flip the sign on some of the $a_{i}$s and make them negative (or rather $p_{i} = -a_{i}$). Then the question is whether this problem is NP-complete.

Of course the answer is yes, we just need to identify a suitable problem for the reduction. In this case, there's a very simple reduction from the Partition problem:

Input: A set of positive integers $S=\{s_{1},\ldots,s_{n}\}$.
Question: Is there a partition of $S$ into two disjoint subsets $S_{1}$ and $S_{2}$ such that $S = S_{1} \cup S_{2}$ and $\sum S_{1} = \sum S_{2}$?

The reduction should be pretty clear from here.

Let $S$ be the input to the Partition instance, then we construct an input set $A$ for the new problem by simply setting $A := S$.

Now we just have to show that $S$ is a Yes-instance for Partition if and only if $A$ is a Yes-instance for the new problem.

Assume $S$ is a Yes-instance for Partition, then there are two sets $S_{1}$ and $S_{2}$ that partition $S$ as described, and importantly have the same sum, then in $P$ we can set the elements corresponding to elements of $S_{2}$ to be negative, and we have a solution for the new problem ($P$ is really just $S$ in disguise, now with some signs flipped to negative).

Now assume $A$ is a Yes-instance for the new problem, then there exists a $P$ which is $A$, but with some elements now negative. Then there is some set $P' \subset P$ whose elements are negative and with a little thought we can see that as $\sum P = 0$ hence $\sum (P\setminus P') + \sum P' = 0$. Therefore, more precisely, $\sum_{p \in P\setminus P'} p = \sum_{q \in P'}|q|$. Obviously if then go back to looking at $A$ (which is just $S$ recall), we have a partition suitable for a solution to the Partition instance.

So we have that Partition $\leq_{m}$ "the new problem", which tells us that the new problem is NP-hard. The very last bit is to show that the new problem is in NP, and hence NP-complete. This is of course simple, as all we have to do is observe that we can check a solution in polynomial-time just by:

  1. Adding up $P$ and checking the sum is zero, and
  2. Checking that each element $p_{i}$ is $\pm a_{i}$.

So, now that I've gone a bit overboard, did I guess the details correctly?

| cite | improve this answer | |

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.