# Is the following Subset Sum variant NP-complete?

Is the following problem NP-hard:

Input: $A\subset\mathbb Z, k\in\mathbb N$
Question: is there a multiset of indices $I$, such that $|I|=k$ and $\sum_{i\in I} a_i=0$?

For example, on the input $A=\{-1,2\}, k=3$ we can take $I=\{1,1,2\}$ and thus we get $|I|=3$ and $a_1+a_1+a_2=(-1)+(-1)+2=0$, as desired.

• I know that there's an easy reduction from Subset Sum problem to inputs of the form $A,k$ where $I$ should be a set. Also, I know that there's an easy reduction from this problem to Subset Sum problem by taking $A$ to be a multiset (each element of $A$ should appear $k$ times in the output of the reduction). But I am stuck showing the required reduction. – Dudi Frid Apr 28 '17 at 13:12
• I think that careful analysis of the standard reduction from Vertex Cover to Subset Sum will show that you can actually use a multiset, and it wouldn't matter. But I didn't check the details, and it seems like an inelegant solution anyway. – Shaull Apr 28 '17 at 13:34
• @orlp, why are you thinking that? Each element of $I$ is supposed to be an index, so in the example it must be either 1 or 2 (as $|A|=2$, i.e., $a_1=-1$, $a_2=2$). – D.W. Apr 28 '17 at 14:31
• @nick.schachter, why does that suggest the problem is not NP-hard? If we were limited to $k=3$, then the results about 3-sum would suggest that the problem is not NP-hard. But in this question $k$ is not limited to $k=3$; $k$ can be arbitrarily large, and thus those methods don't yield a polynomial-time algorithm. – D.W. Apr 29 '17 at 0:42
• If 0 is present in $A$, the answer is trivially yes if I correctly understood the problem. (However, the case "at most k" may still be interesting to study). – user53923 May 2 '17 at 9:36

It is NP-hard.

Consider the following two variants:

Variant 1:

Input: $A\subset\mathbb N$, $s\in\mathbb N$.
Question: is there a set of indices $I$, $\sum_{i\in I} a_i=s$?

Variant 2:

Input: $A\subset\mathbb N$, $k\in\mathbb N$, $s\in\mathbb N$.
Question: is there a multiset of indices $I$, such that $|I|=k$ and $\sum_{i\in I} a_i=s$?

It is easy to see variant 1 is NP-hard. It is also easy to reduce variant 2 to your variant in polynomial time by transforming each element $e$ in an instance of variant 2 to $ke-s$. So if we can prove there is a polynomial-time reduction from variant 1 to variant 2, the proof is completed.

The reduction from variant 1 to variant 2 is exactly the same as the one posted by Kristoffer Arnsfelt Hansen in this answer. I rewrite it here for consistency of symbols.

Given an instance of variant 1, assume that $a_i < B$ for all $i$. We will have two new elements for each old element, simulating whether the element is used 0 or 1 times. For element $a_i$ we get two new elements $a^1_i = (2^{n+1} + 2^i)nB + a_i$ and $a^0_i = (2^{n+1} + 2^i)nB$. The new target sum is defined as $s' = (n2^{n+1} + 2^n + \dots + 2^1)nB + s$. The number of elements required in a solution is set to be $n$.

Note in a valid solution of the new instance, for each $i$, the number of $a_i^1$ and that of $a_i^0$ must be exactly $1$ in total, so there is exactly $n$ elements in a valid solution. This is indeed a polynomial-time reduction from variant 1 to variant 2.

Assuming that the algorithm for your problem returns the yes/no answer together with the actual multi-set $I$ itself, then we can build a reduction from sub-set sum to your problem by sending your algorithm several $k$'s starting with $k=N,(|A|=N)$ down to $k=2$, where each time we check for repetitiveness to make sure we have a valid minimum sub-set sum. That would be running your algorithm $N-1$ times each time checking validity which sums up to $N(N-1)$ times your algorithm's running time. Conclusion, your problem is NP-Hard.

Note: Even if your algorithm does not return the actual sub multi-set it can be obtained by repeatedly removing one of the set's elements and checking that the sub multi-set still exists.

• How do you handle repetitiveness? Could you please explain more? – xskxzr Mar 11 '18 at 8:18