Take the 2-minute tour ×
Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It's 100% free, no registration required.

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.

share|improve this question

1 Answer 1

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.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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