1
$\begingroup$

The subset sum problem is NP Complete. I was wondering if the following variation can be proved to be NP Complete :

The cardinality of set of integers is $m$. And each element of the set is between $1$ and $m^2$. Repetitions are allowed. The objective is to find a subset that would sum up to a given sum.

This seems to be as hard as the subset sum itself, but i cant come up with a reduction that would prove my conjecture.

|cite|improve this question
$\endgroup$

closed as off topic by Jukka Suomela, Mohammad Al-Turkistany, Kaveh May 7 '11 at 20:39

Questions on Theoretical Computer Science Stack Exchange are expected to relate to research-level theoretical computer science within the scope defined by the community. Consider editing the question or leaving comments for improvement if you believe the question can be reworded to fit within the scope. Read more about reopening questions here. If this question can be reworded to fit the rules in the help center, please edit the question.

  • 2
    $\begingroup$ Voted to close as off-topic; not a research-level question. This seems to be a variant that is easy to solve using dynamic programming. $\endgroup$ – Jukka Suomela May 7 '11 at 14:13
  • $\begingroup$ so solvable using dp implies a polynomial time algorithm right? $\endgroup$ – AnkurVj May 7 '11 at 15:06
  • 1
    $\begingroup$ No, but in this case it is a polynomial-time algorithm. $\endgroup$ – Jukka Suomela May 7 '11 at 15:56
  • $\begingroup$ I don't know if you have read the FAQ but this site is for research-level questions in theoretical computer science. Please refer to the FAQ for further information about the scope of cstheory. Closing the question as off-topic. $\endgroup$ – Kaveh May 7 '11 at 20:39