16
$\begingroup$

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?
$\endgroup$
  • 5
    $\begingroup$ 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 $\endgroup$ – domotorp Nov 12 '13 at 16:01
  • 3
    $\begingroup$ 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 $\endgroup$ – Sasho Nikolov Nov 12 '13 at 20:22
  • 8
    $\begingroup$ 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. $\endgroup$ – Andrej Bauer Nov 13 '13 at 19:12
  • 6
    $\begingroup$ 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. $\endgroup$ – Sasho Nikolov Nov 13 '13 at 21:06
  • 4
    $\begingroup$ @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). $\endgroup$ – Tyson Williams Nov 14 '13 at 14:18
1
$\begingroup$

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.

$\endgroup$
0
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ 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: en.wikipedia.org/wiki/Knapsack_problem#Dynamic_programming $\endgroup$ – domotorp Nov 13 '13 at 20:08
  • 2
    $\begingroup$ @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? $\endgroup$ – Sasho Nikolov Nov 13 '13 at 21:11
  • 1
    $\begingroup$ 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: cs.utexas.edu/~klivans/focs11.pdf $\endgroup$ – Sasho Nikolov Nov 13 '13 at 21:15
  • 3
    $\begingroup$ 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. $\endgroup$ – 4evergr8ful Nov 20 '13 at 4:13

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.