<p>Regarding (1), the problem is not strongly NP-hard, c.f. Corollary 1 in <a href="http://dl.acm.org/citation.cfm?id=322287" rel="nofollow">here</a>:</p>

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

<p>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 <a href="http://www.sciencedirect.com/science/article/pii/S030439750800710X" rel="nofollow">here</a>:</p>

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

<p>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.</p>

CC BY-SA 3.0
2015-09-30T11:54:47.787Z
2015-09-30T11:54:47.787Z
Christoph Haase
<p>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 <a href="https://math.stackexchange.com/questions/30638/count-the-number-of-positive-solutions-for-a-linear-diophantine-equation">Count the number of positive solutions for a linear diophantine equation</a>. The stuff is related to Erhart polynomials, which I know nothing about, and I think also to @SashoNikolov's comments above.</p>

<p>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 &amp; \text{if $a_1 \mid b$} \\\\
0 &amp; \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.</p>

CC BY-SA 3.0
2013-11-13T20:08:02.073Z
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
CC BY-SA 3.0
2013-11-13T21:11:52.997Z
@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
CC BY-SA 3.0
2013-11-13T21:15:13.683Z
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
CC BY-SA 3.0
2013-11-20T04:13:19.373Z
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
CC BY-SA 3.0
2013-11-13T19:45:53.933Z
2013-11-13T20:05:17.737Z
2017-04-13T12:19:19.363Z
Andrej Bauer
<p>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 <em>Theory of Linear and Integer Programming</em>. And even then, it's a rather terse discussion.</p>

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

<p>There are two questions I mostly care about:</p>

<ol>
<li>Is it strongly NP-Complete?</li>
<li>Is the related problem of counting the number of solutions #P-hard, or even #P-complete? </li>
</ol>

CC BY-SA 3.0
2013-11-12T16:01:01.293Z
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
CC BY-SA 3.0
2013-11-12T20:22:41.043Z
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
CC BY-SA 3.0
2013-11-12T23:21:36.910Z
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
CC BY-SA 3.0
2013-11-12T23:52:06.563Z
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
CC BY-SA 3.0
2013-11-13T00:50:20.540Z
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
CC BY-SA 3.0
2013-11-13T14:21:58.960Z
@4evergr8ful "Garey and Johnson said they had the hunch that every transformation could be made parsimonious." Is this quote published?
Tyson Williams
CC BY-SA 3.0
2013-11-13T19:12:30.190Z
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
CC BY-SA 3.0
2013-11-13T19:58:58.690Z
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
CC BY-SA 3.0
2013-11-13T20:11:54.277Z
@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
CC BY-SA 3.0
2013-11-13T20:28:13.137Z
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
CC BY-SA 3.0
2013-11-13T21:06:12.887Z
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
CC BY-SA 3.0
2013-11-13T21:34:44.347Z
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
CC BY-SA 3.0
2013-11-14T01:07:09.727Z
@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
CC BY-SA 3.0
2013-11-14T14:18:41.533Z
@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
CC BY-SA 3.0
2013-11-15T03:09:26.580Z
@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
CC BY-SA 3.0
2014-11-09T16:38:11.303Z
The unbounded Knapsack problem has been covered in a [previous question](http://cstheory.stackexchange.com/questions/1000/simple-reduction-to-unbounded-knapsack/1002#1002)
Kristoffer Arnsfelt Hansen
<cc.complexity-theory><reference-request><np-hardness><counting-complexity>
Linear diophantine equation in non-negative integers
4evergr8ful
# Linear diophantine equation in non-negative integers

(Asked by: username_0 on 2013-11-12)

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?

**Tags:** cc.complexity-theory, reference-request, np-hardness, counting-complexity

> **Comments:**
> **username_1**: 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  
> **username_2**: 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  
> **username_0**: username_1: 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.  
> **username_0**: username_2: 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?  
> **username_0**: username_2: 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.  
> **username_3**: @username_0 "Garey and Johnson said they had the hunch that every transformation could be made parsimonious." Is this quote published?  
> **username_4**: May I please ask both @username_1 and username_0 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 username_0 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.  
> **username_0**: username_3: 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.  
> **username_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.  
> **username_5**: 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?  
> **username_2**: 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 username_1 had a good reason to point you to the knapsack wiki page.  
> **username_5**: 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.  
> **username_0**: @Sasho, Austin, username_1 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.  
> **username_3**: @username_0 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).  
> **username_0**: @username_3 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...".  
> **username_6**: The unbounded Knapsack problem has been covered in a [previous question](http://cstheory.stackexchange.com/questions/1000/simple-reduction-to-unbounded-knapsack/1002#1002)  

---

## 2 answers

### Answer by username_7 on 2015-09-30. Score: 1

Regarding (1), the problem is not strongly NP-hard, c.f. Corollary 1 in [here](http://dl.acm.org/citation.cfm?id=322287):

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](http://www.sciencedirect.com/science/article/pii/S030439750800710X):

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.


---

### Answer by username_4 on 2013-11-13. Score: 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](https://math.stackexchange.com/questions/30638/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.

> **Comments:**
> **username_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  
> **username_2**: @username_1, 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?  
> **username_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  
> **username_0**: 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.  

---

