# Is this modification of the subset-sum problem NP-complete?

Suppose we have input $s_1,\dots,s_n \in \mathbb Z$ and $t \in \mathbb Z$. We want to know if there exist variables $x_1,\dots,x_n$ in which each $x_i=1/2^k$, where $k \in \{0,1,2,3,4,\dots,\infty\}$, such that $s_1x_2+\dots+s_nx_n=t$.

Is this problem NP-complete? Is it solvable in polynomial-time?

• My guess is NP-complete. Indeed, it is not hard (but not completely trivial) to show that it is in NP (we need an upper bound on $k$). NP-hardness is the harder part – have you tried proving that your problem is NP-hard? – Yuval Filmus Oct 27 '14 at 3:57
• No, I haven't tried. – Craig Feinstein Oct 27 '14 at 13:34
• This variant of subset-sum has probably never appeared before, so all an answerer can do is try to prove its NP-hardness. It makes more sense for you to try first, and come back to the community only if you get stuck after a while. – Yuval Filmus Oct 27 '14 at 14:37