Linear diophantine equation in non-negative integers 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:


Is it strongly NP-Complete?
Is the related problem of counting the number of solutions #P-hard, or even #P-complete?
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 &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.