Timeline for Linear diophantine equation in non-negative integers
Current License: CC BY-SA 3.0
26 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Sep 30, 2015 at 11:54 | answer | added | Christoph Haase | timeline score: 1 | |
| Aug 1, 2015 at 8:38 | review | Suggested edits | |||
| Aug 1, 2015 at 13:23 | |||||
| Nov 9, 2014 at 16:38 | comment | added | Kristoffer Arnsfelt Hansen | The unbounded Knapsack problem has been covered in a previous question | |
| Nov 9, 2014 at 7:48 | review | Close votes | |||
| Nov 10, 2014 at 4:14 | |||||
| Nov 15, 2013 at 3:09 | comment | added | 4evergr8ful | @Tyson Williams Yes that's right. I'd forgotten about these cases. I would also blame Garey and Johnson for taking liberties with these 6 problems. They could have said "for instance it can be shown...". | |
| Nov 14, 2013 at 14:18 | comment | added | Tyson Williams | @4evergr8ful Sure, I assumed that you paraphrased the quote. That is ok. However, you have misquoted them by changing "six" to "every". As G&J define parsimonious (i.e. the number of solutions is exactly the same), it is NOT true that every reduction between problems in NP can be made parsimonious UNLESS P = Parity-P. The reason for this is that the standard reduction from SAT to NAE-SAT introduces a factor which is a power of 2. This is expected, since SAT is complete for Parity-P but NAE-SAT is easy (there is an obvious pairing of assignments so the answer is always even = 0). | |
| Nov 14, 2013 at 1:07 | comment | added | 4evergr8ful | @Sasho, Austin, domotorp I agree, it can be modeled as an unbounded knapsack instance. I only knew about the classical knapsack which is over 0 1 values. Not something I could easily have found by googling however. | |
| Nov 13, 2013 at 21:34 | comment | added | Austin Buchanan | Are we sure this problem is even weakly NP-complete? Supposedly unbounded knapsack is NP-hard by G.S. Lueker, Two NP-Complete Problems in Nonnegative Integer Programming, Report No. 178, Computer Science Laboratory, Princeton University, 1975, but I cannot access it to see if the reduction applies to your problem. | |
| Nov 13, 2013 at 21:06 | comment | added | Sasho Nikolov | OP, as @Austin mentioned, the same dynamic program idea as for knapsack works to solve your problem in polynomial time when the $a_i$ are polynomial bounded. so, no, the problem is not strongly np-complete. and domotorp had a good reason to point you to the knapsack wiki page. | |
| Nov 13, 2013 at 20:28 | comment | added | Austin Buchanan | For question 1: this is the unbounded knapsack problem, right? The wikipedia page points out that you can apply the dynamic programming algorithm. So, it is not likely to be strongly NP-complete, right? | |
| Nov 13, 2013 at 20:11 | comment | added | domotorp | @Andrej: I am happy to hear that someone asks more civility. Half of the people simply comment "Is this homework?" if they find a problem too easy. While I strongly disagree with them, I do think that some questions that are too easy (for say, anyone who has taken a graduate course on the topic) should not be answered on this forum. | |
| Nov 13, 2013 at 19:58 | comment | added | 4evergr8ful | Tyson Williams: That's how I wrote it to make a story short. Depending on how you interpret it, they implicitly did it by saying without proof "We can thus conclude, for example, that the enumeration problems associated with the six basic NP-complete problems of Chapter 3 are #P-complete." at p.169 in Computers and Intractability. | |
| Nov 13, 2013 at 19:45 | answer | added | Andrej Bauer | timeline score: 1 | |
| Nov 13, 2013 at 19:17 | history | edited | Andrej Bauer | CC BY-SA 3.0 |
markdown
|
| Nov 13, 2013 at 19:12 | comment | added | Andrej Bauer | May I please ask both @domotorp and 4evergr8ful for a bit more civility? The first one could have explained how the knapsack problem reduces to such Diophantine equations, which he seems to think is the case, while 4evergr8ful could perhaps cool down, especially since he is both asking for help and is obviously inexpirienced in the workings of this forum. But I thought about the knapsack problem too, and it is not clear to me at all that it reduces to positive solutions of Diophantine equations. | |
| Nov 13, 2013 at 14:21 | comment | added | Tyson Williams | @4evergr8ful "Garey and Johnson said they had the hunch that every transformation could be made parsimonious." Is this quote published? | |
| Nov 13, 2013 at 0:50 | comment | added | 4evergr8ful | Sasho Nikolov: Although I did thank you for the link, I should have been more appreciative. In terms of known transformations these problems are indeed close. And, at a glance, the paper you referenced might be helpful. Now if anyone knows about the strong NP-completeness status, that would make my day. | |
| Nov 12, 2013 at 23:52 | comment | added | 4evergr8ful | Sasho Nikolov: Thanks for the link. I don't believe that any pair of problems is more closely related to one another than any other pair. It's all the same problem viewed from different angles (so what I'm interested in is the particular angle of attack called "diophantine equation"). Subset sum looks closer to diophantine equation but that's just intuition failing us. Garey and Johnson said they had the hunch that every transformation could be made parsimonious. As far as I know it has never been proved. The transformation given in Schrijver is not parsimonious. Are there known techniques? | |
| Nov 12, 2013 at 23:21 | comment | added | 4evergr8ful | domotorp: There's nothing about this problem in your link. Do you seriously believe that all research stops at the Knapsack problem? You know, every darn NP-complete problem polynomially reduces to the Knapsack problem. So we might as well stop discussing such problems until someone comes up with the revelation about the P vs NP question. | |
| Nov 12, 2013 at 20:22 | comment | added | Sasho Nikolov | for 2), afaik there is no known example of an NP-complete problem whose natural counting version is not #P-complete. figuring out a parsimonious reduction for your particular problem might be easier than finding a reference. this paper does it for the closely related #SubsetSum: crt.umontreal.ca/~gerardo/tsppd-p-complete.pdf | |
| Nov 12, 2013 at 16:15 | review | Close votes | |||
| Nov 17, 2013 at 3:04 | |||||
| Nov 12, 2013 at 16:01 | comment | added | domotorp | This is really not a research level question and I find it hard to believe that you did not find more information. Start here: en.wikipedia.org/wiki/Knapsack_problem | |
| Nov 12, 2013 at 13:01 | history | tweeted | twitter.com/#!/StackCSTheory/status/400246906720616448 | ||
| Nov 12, 2013 at 7:43 | review | First posts | |||
| Nov 12, 2013 at 17:10 | |||||
| Nov 12, 2013 at 7:33 | history | edited | 4evergr8ful |
edited tags
|
|
| Nov 12, 2013 at 7:23 | history | asked | 4evergr8ful | CC BY-SA 3.0 |