Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It only takes a minute to sign up.
Sign up to join this community
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.
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.
