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

<p>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.</p>

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

CC BY-SA 3.0
2011-05-07T14:13:59.363Z
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](http://en.wikipedia.org/wiki/Subset_sum_problem#Pseudo-polynomial_time_dynamic_programming_solution).
Jukka Suomela
CC BY-SA 3.0
2011-05-07T15:06:13.800Z
so solvable using dp implies a polynomial time algorithm right?
AnkurVj
CC BY-SA 3.0
2011-05-07T15:56:54.947Z
No, but in *this* case it is a polynomial-time algorithm.
Jukka Suomela
CC BY-SA 3.0
2011-05-07T20:39:22.127Z
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.
Kaveh
<ds.algorithms><np-hardness>
A variation of the subset sum problem
AnkurVj
# A variation of the subset sum problem

(Asked by: username_0 on 2011-05-07)

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.

**Tags:** ds.algorithms, np-hardness
> **Comments:**
> **username_1**: 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](http://en.wikipedia.org/wiki/Subset_sum_problem#Pseudo-polynomial_time_dynamic_programming_solution).  
> **username_0**: so solvable using dp implies a polynomial time algorithm right?  
> **username_1**: No, but in *this* case it is a polynomial-time algorithm.  
> **username_2**: 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.  

---

## 0 answers

