17
$\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?
Improve this question
$\endgroup$
16
  • 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
    Commented Nov 12, 2013 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
    Commented Nov 12, 2013 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
    Commented Nov 13, 2013 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
    Commented Nov 13, 2013 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
    Commented Nov 14, 2013 at 14:18

2 Answers 2

Reset to default
1
$\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.

Improve this answer
$\endgroup$
4
  • 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
    Commented Nov 13, 2013 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
    Commented Nov 13, 2013 at 21:11
  • 2
    $\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
    Commented Nov 13, 2013 at 21:15
  • 5
    $\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
    Commented Nov 20, 2013 at 4:13
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.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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