3
$\begingroup$

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?

|cite|improve this question
$\endgroup$
  • 1
    $\begingroup$ Hint: $d = 1$ should suffice. $\endgroup$ – Yuval Filmus Jun 13 '14 at 17:24
  • 1
    $\begingroup$ Do you know how to such reductions in general? You could combine Yuval's great hint with this, and most likely solve the problem :-) $\endgroup$ – Juho Jun 13 '14 at 17:27
  • $\begingroup$ @YuvalFilmus I've considered the case for $d=1$. But this leaves me with the following question: for a set of integers X, does there exist a k-element subset S of X such that $\sum_S$ is a power of two? How to show that this is NP-Complete is not clear to me, because the Subset Sum problem with a fixed subset size is not NP-complete. I don't see the immediate reduction. I assume I have to show that while the fixed subset reduces the computational complexity of the problem, the "is a power of two" adds complexity so that the overall problem is still NP-Complete? Your input would be appreciated. $\endgroup$ – Newb Jun 13 '14 at 18:22
  • $\begingroup$ @Juho do you have any suggestions how to tackle this? $\endgroup$ – Newb Jun 13 '14 at 20:11
  • 1
    $\begingroup$ Is $k$ a constant or an input? That is, can the solution run in time $\Theta(n^k)$ or must it run in time polynomial in $k$? $\endgroup$ – gardenhead Jun 13 '14 at 22:57
3
$\begingroup$

Here are some hints:

  1. Focus on the case $d = 1$.

  2. 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.

  3. 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.

|cite|improve this answer
$\endgroup$
  • $\begingroup$ Hint #3 was extremely helpful. Thanks! $\endgroup$ – Newb Jun 14 '14 at 2:50
  • $\begingroup$ Now I am just wondering about the second part of your hint: changing a target is helpful, but I don't see how it lets me generalize to any power of two, rather than a specific one... $\endgroup$ – Newb Jun 14 '14 at 19:14
  • $\begingroup$ @Newb You're right, my hints don't address this issue. Time for you to think. $\endgroup$ – Yuval Filmus Jun 14 '14 at 22:46
2
$\begingroup$

Hint #1: focus on $d=1$, as Yuval suggests.

Hint #2: suppose we're given an instance of the subset-sum problem, i.e., we're given some integers $x_1,x_2,\dots,x_n$.

Now suppose we let $v_1=42x_1$, ..., $v_n = 42x_n$. Think about whether there is a subset of $\{v_1,\dots,v_n\}$ that sums to a power of two. When does that happen? What's the condition under which $\{v_1,\dots,v_n\}$ has a subset that sums to a power of two?

The answer looks unhelpful, but notice that $42$ is arbitrary. What if we replace $42$ with some other constant $c$, and then ask the same question? Can you find some other constant $c$ (instead of $42$) where the condition when $\{v_1,\dots,v_n\}$ has a subset that sums to a power of two is more convenient?

Hint #3: to start with, I suggest you artificially consider $0$ to be a power of two (even though I know it isn't really a power of two) and you ignore the constraint on the size of the subset. Once you can solve that variation, I suggest you go back to the original problem: a slight tweak to your construction should take care of them.

Reminder: Don't forget to attribute all your sources, when you write up the solution to your exercise. Your teachers read the Internet too. :-)

|cite|improve this answer
$\endgroup$
  • $\begingroup$ Interesting. Your hint w/r/t/ the constant has really given me something to think about... $\endgroup$ – Newb Jun 14 '14 at 3:42
  • $\begingroup$ The constant is giving me some trouble, and I can't see how this leads to the solution. I've fiddled with prime factorizations, adding/removing terms, etc., but I still don't see how the constant helps to find whether or not the subset sums to a power of two, even for the smallest power, $2^0=1$. $\endgroup$ – Newb Jun 14 '14 at 4:39

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.