patternMinor
Is the following Subset Sum variant NP-complete?
Viewed 0 times
variantthefollowingcompletesumsubset
Problem
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.
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.
Solution
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.
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.
Context
StackExchange Computer Science Q#74661, answer score: 2
Revisions (0)
No revisions yet.