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?