Showing a partition-like problem is NP-complete

Question

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.

Answer 1

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:

Partition
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?