Timeline for Complexity of a subset sum variant
Current License: CC BY-SA 3.0
14 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Jan 30, 2014 at 23:04 | answer | added | Marzio De Biasi | timeline score: 3 | |
| Jan 29, 2014 at 10:31 | history | edited | Mohammad Al-Turkistany |
added a tag
|
|
| Nov 22, 2011 at 14:20 | history | tweeted | twitter.com/#!/StackCSTheory/status/138985313761640448 | ||
| Nov 16, 2011 at 1:44 | comment | added | Jukka Suomela | A spoiler: A very simple way to show the NP-hardness of the usual 0-1 subset sum problem is a reduction from the exact cover problem. Now you can take the usual reduction and tweak it a bit to make sure that any non-0-1 solution is infeasible. In essence, you can first make sure that $\sum_i x_i > m$ is infeasible, and then make sure that $1 < x_i \le m$ is infeasible for each $i$. | |
| Nov 16, 2011 at 1:05 | answer | added | Tsuyoshi Ito | timeline score: 12 | |
| Nov 16, 2011 at 0:01 | comment | added | Marcos Villagra | aah I see that now after looking more closely :-) | |
| Nov 15, 2011 at 22:29 | answer | added | domotorp | timeline score: 7 | |
| Nov 15, 2011 at 21:55 | history | edited | Tsuyoshi Ito | CC BY-SA 3.0 |
seeming typo
|
| Nov 15, 2011 at 20:17 | comment | added | v s | $\exists b': \forall b > b' \in \mathbb{N} : \sum_{i=1}^{n}x_{i}a_{i}=b$ always has solutions $x_{i} \in \mathbb{N} \cup 0$ when $a_{i} \in \mathbb{N}$. I do not think removing $0$ from possible candidates for $x_{i}$ would change the result. So deciding whether there is a solution or not depends on $a_{i}$, $b$ and $n$. When $n = 2$, the answer is known if $x_{i}$ takes $0$ as well. Look at Kannan's work on the Frobenius problem. I think it is in Poly. But I am not 100% sure. | |
| Nov 15, 2011 at 18:15 | comment | added | Stasys | @Marcos Villagra: Indeed, what is a (simple) reduction of 0-1 subset sum problem to this "multiple subset sum" problem? (The converse reduction is trivial: just take $n$ copies of each $a_i$.) If this is a homework, then it is not a bad one. | |
| Nov 15, 2011 at 4:04 | comment | added | Suresh Venkat | @MarcosVillagra: the reduction from SUBSET SUM is not obvious because the solution produced by this problem might not have only 0-1 weights | |
| Nov 15, 2011 at 0:37 | comment | added | Marcos Villagra | this is like a subset-sum with integer weights. Since the original subset problem (i.e., the weights are all 1) is NP-complete, then this version is also NP-complete. | |
| Nov 14, 2011 at 21:33 | comment | added | Jukka Suomela | Could you perhaps give us a bit more background? In the present form the question sounds like a homework problem, in which case it would be off-topic here. | |
| Nov 14, 2011 at 21:01 | history | asked | Paul | CC BY-SA 3.0 |