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?