6
$\begingroup$

My question is simply, can linear Diophantine equations be solved in polynomial time? Specifically, I am looking at equations of the form $a_1 x_1+a_2 x_2 + ... + a_n x_n = k$, where $a_i,x_i,k$ are all integers, and solving for $x_i$. The algorithm I am using is based off of the following journal article:

http://www.jstor.org/stable/3620787 .

The algorithm I derived from the article is roughly as follow:

  1. Find a minimum coefficient (there could be many, just pick the any of them).
  2. Take every coefficient that is not the one you picked in the modulus of coefficient you picked.
  3. Check if any coefficients are 1, if so, go to 5.

  4. Go to 1.

  5. Back-substitute to find solution.

Currently, I have an incomplete argument that the algorithm is indeed polynomial time. My argument is as follows:

Suppose we choose the $a_j$ that such that it minimizes the number of bits all of the coefficients are reduced by, thereby maximizing the number of iterations. Then, after we compute ${a^{'}_{{i} \neq {j}} = a_{{i} \neq {j}}} \mod {a_j}$ we know that $a^{'}_{{i} \neq {j}} < {{a_{{i} \neq {j}}} \over {2}}$, because if it were not, then $a_j$ could go into $a_{{i} \neq {j}}$ another time. On the next iteration, the previous minimum $a_j$ cannot be the new minimum, since every other coefficient is less. Thus, the previous minimum will necessarily be reduced by one bit. Hence, all of the coefficients are reduced by at least 1 bit every 2 iterations. Thus, the maximum number of iterations is twice the maximum number of bits for a coefficient $2\log_2(\max {a_i})$, the back-substitution takes exactly the same number of steps, thus I estimate the algorithm is $O(\log(\max {a_i}))$, which is polynomial time with respect to the number of bits in the coefficient representation.

Am I missing something or is this correct? Please let me know if there is anything I need to clarify.

$\endgroup$

1 Answer 1

8
$\begingroup$

Yes, this class of equations can be solved in polynomial time. In particular, there exists a solution if and only $\gcd(a_1,\dots,a_n)$ divides $k$. That condition can be tested in polynomial time, since there are polynomial-time algorithms to compute the gcd. In addition, if a solution exists, one can be found using the extended Euclidean algorithm.

$\endgroup$
2
  • $\begingroup$ Could you please point to any resource where I can read about this in better detail? I want to find all integer solutions to a $n$-variable linear diophantine equation (like in this question), where each variable is restricted to a finite interval. This question and answer are the only useful resource I have managed to find so far. I would like to read about the condition you mentioned in the answer, the use of the extended Euclidean algorithm, and its complexity. Thank you in advance. $\endgroup$
    – GoodDeeds
    Mar 29, 2018 at 19:39
  • 1
    $\begingroup$ @GoodDeeds, You could read about the extended Euclidean algorithm, which I mentioned in my answer. You can find many resources on that. I suggest you start by understanding the case $n=2$ -- that's covered in the standard resources. Then, start thinking about the case $n=3$ and see what you can come up with, and if you get stuck, ask a new question and show us what you've read, what progress you've made so far, and what specifically you are stuck/unsure on. The restriction to a specific interval might change the problem; I don't know, and I haven't thought about it. $\endgroup$
    – D.W.
    Mar 29, 2018 at 19:50

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.