Timeline for Complexity of an algorithm to solve linear diophantine equations
Current License: CC BY-SA 3.0
5 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Oct 1, 2014 at 17:19 | comment | added | user39115 | Yes, yes, it is polynomial, but, I think there is maybe an explicit formula? | |
| Oct 1, 2014 at 15:53 | comment | added | Emil Jeřábek | If $h$ is given in binary, the result may be exponentially large, hence you cannot do better than exponential time. If $h$ is given in unary, you can easily compute the result in polynomial time using the recurrence $S_{h,a_1,\dots,a_{n+1}}=\sum_{j\le h/a_{n+1}}S_{h-ja_{n+1},a_1,\dots,a_n}$. | |
| Oct 1, 2014 at 15:44 | history | edited | user39115 | CC BY-SA 3.0 |
edited title
|
| Oct 1, 2014 at 15:32 | comment | added | user39115 | My guess is that depends on some kind of variance of the $(a_1,\ldots,a_n).$ For example, if all of them are equal the problem is trivial and it s getting more complicated when we start changing one then two etc... | |
| Oct 1, 2014 at 15:26 | history | asked | user39115 | CC BY-SA 3.0 |