patternMinor
Need Help Reducing Subset Sum to Show a Problem is NP-Complete
Viewed 0 times
showproblemneedhelpreducingcompletesumsubset
Problem
I want to show that the following problem is NP-Complete:
For a set of vectors $v_1,\ldots,v_n \in \mathbb{N}^d$ and an integer $k$, does there exist a subset $S \subseteq \{v_1,\ldots,v_n\}$, such that $S$ has $k$ elements and all coordinates in the vector $\sum\limits_{x\in S} v_x$ are powers of two?
I'm quite certain that establishing a reduction from a known NP-Complete problem: the Knapsack Problem, Subset Sum or Vector Subset Sum (see section 4.3 here) to this problem is the correct way to approach this problem, but I'm having difficulty
figuring out how to exactly construct the reduction.
Concerning Subset Sum with a set $S$ and an integer $n$, I've tried taking one of the integer compositions of $n$, then splitting it up into its binary representation, and using that to dictate a desired vector. Then I would construct vectors $v_1,\ldots,v_n$ from the elements of $S$. But how do I create the input $k$?
One of the main issues here is that Subset Sum with a fixed subset size is not NP-complete. How do I work around that? Moreover, one of the trickier aspects of the problem is generalizing subset sum such that success is reported if some subset sums to any power of two. I don't see how not to appeal to multiple sub-instances of subset sum...
Is this the right approach? (If not, how should I do it?) What am I missing? How do I prove this?
For a set of vectors $v_1,\ldots,v_n \in \mathbb{N}^d$ and an integer $k$, does there exist a subset $S \subseteq \{v_1,\ldots,v_n\}$, such that $S$ has $k$ elements and all coordinates in the vector $\sum\limits_{x\in S} v_x$ are powers of two?
I'm quite certain that establishing a reduction from a known NP-Complete problem: the Knapsack Problem, Subset Sum or Vector Subset Sum (see section 4.3 here) to this problem is the correct way to approach this problem, but I'm having difficulty
figuring out how to exactly construct the reduction.
Concerning Subset Sum with a set $S$ and an integer $n$, I've tried taking one of the integer compositions of $n$, then splitting it up into its binary representation, and using that to dictate a desired vector. Then I would construct vectors $v_1,\ldots,v_n$ from the elements of $S$. But how do I create the input $k$?
One of the main issues here is that Subset Sum with a fixed subset size is not NP-complete. How do I work around that? Moreover, one of the trickier aspects of the problem is generalizing subset sum such that success is reported if some subset sums to any power of two. I don't see how not to appeal to multiple sub-instances of subset sum...
Is this the right approach? (If not, how should I do it?) What am I missing? How do I prove this?
Solution
Here are some hints:
-
Focus on the case $d = 1$.
-
Given a target $T$ in SUBSET-SUM, we can change it to a target $T'$ by adding the number $T' - T$; this should work if $T'$ is sufficiently large.
-
Given a SUBSET-SUM without constraints on the size of the subset, we can get an equivalent problem with such a constraint by adding a suitable number of zeroes to the (multi)set.
If we insist on a set, we need to do more cunning in 3.
-
Focus on the case $d = 1$.
-
Given a target $T$ in SUBSET-SUM, we can change it to a target $T'$ by adding the number $T' - T$; this should work if $T'$ is sufficiently large.
-
Given a SUBSET-SUM without constraints on the size of the subset, we can get an equivalent problem with such a constraint by adding a suitable number of zeroes to the (multi)set.
If we insist on a set, we need to do more cunning in 3.
Context
StackExchange Computer Science Q#27663, answer score: 4
Revisions (0)
No revisions yet.