Given a SUBSET-SUM instance $S$ with a weight $W$, is it possible to create, in polynomial time, a new non-empty instance $T$ (at most the same length as $S$) with weight $M$, that for each non-empty subset of set $T$ and its sum $s$, it has a unique $(s-M)^2$, and that a subset of $T$ adds up to $M$ iff a subset of $S$ adds up to $W$?

  • $\begingroup$ Is $M$ an input or an output? Can it be freely chosen by the algorithm? $\endgroup$ – D.W. Sep 16 at 4:34
  • $\begingroup$ If there exists such a reduction, then the variant of subset sum problem where each subset has a unique sum would be NP-complete. Unfortunately, no one has proved or disproved it. $\endgroup$ – xskxzr Sep 16 at 10:41
  • $\begingroup$ @D.W. It's an output, it only depends on $S$ and $W$. $\endgroup$ – DUO Sep 16 at 14:25
  • $\begingroup$ @xskxzr I edited it, so it may be easier to prove (or disprove). $\endgroup$ – DUO Sep 16 at 15:03

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.