17

There's only very little information I can find on the NP-complete problem of solving linear diophantine equation in non-negative integers. That is to say, is there a solution in non-negative $x_1,x_2, ... , x_n$ to the equation $a_1 x_1 + a_2 x_2 + ... + a_n x_n = b$, where all the constants are positive? The only noteworthy mention of this problem that I know of is in Schrijver's Theory of Linear and Integer Programming. And even then, it's a rather terse discussion.

So I would greatly appreciate any information or reference you could provide on this problem.

There are two questions I mostly care about:

  1. Is it strongly NP-Complete?
  2. Is the related problem of counting the number of solutions #P-hard, or even #P-complete?
Andrej Bauer
  • 28,823
  • 1
  • 80
  • 133
4evergr8ful
  • 319
  • 2
  • 4
  • 5
    This is really not a research level question and I find it hard to believe that you did not find more information. Start here: http://en.wikipedia.org/wiki/Knapsack_problem – domotorp Nov 12 '13 at 16:01
  • 3
    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: http://www.crt.umontreal.ca/~gerardo/tsppd-p-complete.pdf – Sasho Nikolov Nov 12 '13 at 20:22
  • 1
    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. – 4evergr8ful Nov 12 '13 at 23:21
  • 1
    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? – 4evergr8ful Nov 12 '13 at 23:52
  • 1
    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. – 4evergr8ful Nov 13 '13 at 00:50
  • @4evergr8ful "Garey and Johnson said they had the hunch that every transformation could be made parsimonious." Is this quote published? – Tyson Williams Nov 13 '13 at 14:21
  • 8
    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. – Andrej Bauer Nov 13 '13 at 19:12
  • 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. – 4evergr8ful Nov 13 '13 at 19:58
  • 1
    @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. – domotorp Nov 13 '13 at 20:11
  • 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? – Austin Buchanan Nov 13 '13 at 20:28
  • 6
    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. – Sasho Nikolov Nov 13 '13 at 21:06
  • 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. – Austin Buchanan Nov 13 '13 at 21:34
  • @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. – 4evergr8ful Nov 14 '13 at 01:07
  • 4
    @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). – Tyson Williams Nov 14 '13 at 14:18
  • @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...". – 4evergr8ful Nov 15 '13 at 03:09
  • The unbounded Knapsack problem has been covered in a previous question – Kristoffer Arnsfelt Hansen Nov 09 '14 at 16:38

2 Answers2

1

I am not an expert on this at all, but I would like to get a constructive discussion started. Here is an attempt, based on the math.stackexchange.com question Count the number of positive solutions for a linear diophantine equation. The stuff is related to Erhart polynomials, which I know nothing about, and I think also to @SashoNikolov's comments above.

Define $N(a_1, a_2, \ldots, a_n; b)$ to be the number of non-negative solutions of the Diophantine equation $$a_n x_n + a_{n-1} x_{n-1} + \cdots + a_1 x_1 = b,$$ where coefficients $a_i$ are positive and $b$ is non-negative. If I am getting my recursions right, then we have $$N(a_1; b) = \begin{cases} 1 & \text{if $a_1 \mid b$} \\\\ 0 & \text{otherwise} \end{cases}$$ and $$N(a_1, \ldots, a_{n+1}; b) = \sum_{0 \leq \ k \ \leq b/a_{n+1}} N(a_1, \ldots, a_n; b - a_{n+1} k) $$ Now, the sum is a bit long (measured in terms of the length of the input), but we might hope to find a better way of computing it than to actually run through all the $k$'s. We know it's going to be a polynomial in $b$, but I do not see how to compute the polynomial fast enough.

Community
  • 1
Andrej Bauer
  • 28,823
  • 1
  • 80
  • 133
  • 1
    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: http://en.wikipedia.org/wiki/Knapsack_problem#Dynamic_programming – domotorp Nov 13 '13 at 20:08
  • 2
    @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? – Sasho Nikolov Nov 13 '13 at 21:11
  • 2
    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: http://www.cs.utexas.edu/~klivans/focs11.pdf – Sasho Nikolov Nov 13 '13 at 21:15
  • 5
    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. – 4evergr8ful Nov 20 '13 at 04:13
1

Regarding (1), the problem is not strongly NP-hard, c.f. Corollary 1 in here:

Papadimitriou, C. H. (1981). On the complexity of integer programming. Journal of the ACM, 28(4), 765-768.

Regarding (2), the problem obviously lies in #P if all constants are positive. There is also a #P-complete version of SubsetSum, which almost fits into your problem instance but does, however, require the $x_i$ to be either 0 or 1, see here:

Faliszewski, P. and Hemaspaandra, L. (2009). The complexity of power-index comparison. Theoretical Computer Science 410(1), 101-107.

I'm pretty sure that the construction used by Faliszewski and Hemaspaandra can be adjusted such that the requirement $x_i\in \{0,1\}$ is not needed and would hence claim that the problem is #P-complete, provided that constants are encoded in binary.

Christoph Haase
  • 371
  • 3
  • 7