Timeline for Linear diophantine equation in non-negative integers
Current License: CC BY-SA 3.0
8 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Apr 13, 2017 at 12:19 | history | edited | CommunityBot |
replaced http://math.stackexchange.com/ with https://math.stackexchange.com/
|
|
| Aug 1, 2015 at 8:38 | review | Suggested edits | |||
| Aug 1, 2015 at 11:48 | |||||
| Nov 20, 2013 at 4:13 | comment | added | 4evergr8ful | I learned one more fact about this problem. There are three kinds of people: those who call it the #linear diophantine problem, those who call it the #unbound knapsack problem, and finally those who call it the denumerant problem. And they don't seem to talk to one another. | |
| Nov 13, 2013 at 21:15 | comment | added | Sasho Nikolov | BTW, I think it's likely that the algorithm in this paper (approximately counting number of solutions for knapsack via dynamic programming) can be adapted to the diophantine equation problem: cs.utexas.edu/~klivans/focs11.pdf | |
| Nov 13, 2013 at 21:11 | comment | added | Sasho Nikolov | @domotorp, I think Andrej is addressing the second question, about #P-completeness, not the first about strong NP-completeness, which, as far as I can see, is very easy to answer (no, the problem is not strongly NP-complete). Andrej, I am confused what you are hoping to show here? Since the decision problem is NP-complete, you cannot hope to count the number of solutions. Are you hoping to approximate the number of solutions? Or have a faster-than-exponential time algorithm? | |
| Nov 13, 2013 at 20:08 | comment | added | domotorp | Dear Andrej, in case of strong NP-hardness, we measure in terms of the value of the input and not in the length of it. See also: en.wikipedia.org/wiki/Knapsack_problem#Dynamic_programming | |
| Nov 13, 2013 at 20:05 | history | edited | domotorp | CC BY-SA 3.0 |
last a_n changed to a_{n+1}
|
| Nov 13, 2013 at 19:45 | history | answered | Andrej Bauer | CC BY-SA 3.0 |