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?

  • $\begingroup$ 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? $\endgroup$ – Yuval Filmus Oct 27 '14 at 3:57
  • $\begingroup$ No, I haven't tried. $\endgroup$ – Craig Feinstein Oct 27 '14 at 13:34
  • 1
    $\begingroup$ 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. $\endgroup$ – Yuval Filmus Oct 27 '14 at 14:37

Your Answer

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

Browse other questions tagged or ask your own question.