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$
  • 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