Timeline for Check if K-Sum Variation is NP-Complete
Current License: CC BY-SA 4.0
Post Revisions
13 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Jan 23, 2019 at 21:45 | vote | accept | tkellehe | ||
| Jan 23, 2019 at 21:31 | answer | added | 喜欢算法和数学 | timeline score: 2 | |
| Jan 23, 2019 at 21:28 | answer | added | D.W.♦ | timeline score: 0 | |
| Jan 23, 2019 at 21:23 | comment | added | D.W.♦ | cs.stackexchange.com/q/11209/755, cs.stackexchange.com/q/1240/755 | |
| Jan 23, 2019 at 20:36 | history | edited | tkellehe | CC BY-SA 4.0 |
trying to be more explicit.
|
| Jan 23, 2019 at 20:35 | comment | added | tkellehe | @Apass.Jack A range of numbers where the minimum of the range is $a$ and the maximum of the range is $b$. So my set includes $a$, $a+1$, ..., $b-1$, $b$. I see where the confusion might be happening. I edited my question. | |
| Jan 23, 2019 at 20:29 | comment | added | 喜欢算法和数学 | Wait. I might not be careful enough. "Given a range of numbers $[a,\cdots,b]$", do you mean a list of number $a_1, a_2, \cdots, c_n$? When we compute the time-complexity, is it in terms of $n$ or in terms of $k$ and $n$? | |
| Jan 23, 2019 at 20:09 | comment | added | tkellehe | So, essentially all I have to say is that the range of numbers is my set for the k-sum problem and it is now NP-Complete? | |
| Jan 23, 2019 at 19:57 | comment | added | tkellehe | Is that sufficient enough to prove that this problem is NP-Complete? I thought it involved more gymnastics than that? | |
| Jan 23, 2019 at 19:26 | comment | added | tkellehe | @Apass.Jack Yes, I am aware of this. And k-sum is essentially the subset sum problem, correct? | |
| Jan 23, 2019 at 18:51 | comment | added | 喜欢算法和数学 | Are you aware the subset sum problem is NP-complete? | |
| Jan 23, 2019 at 18:45 | review | First posts | |||
| Jan 23, 2019 at 18:51 | |||||
| Jan 23, 2019 at 18:41 | history | asked | tkellehe | CC BY-SA 4.0 |