CODEWITHSUNDEEP
algorithmtime-complexity
rubyquartz
rubyquartz

Reputation: 321

Complexity of solving a Diophantine equation with potential solutions

Say I have an equation, given as

13x + 5y = M, where M is given each time.

Evidently this is a diophantine equation and could take a long time to solve depending on the case. However, a reading told me that if we have a set of unique integer "possible solutions" of size k for X and Y stored in a Binary search tree (meaning the correct values for X and Y are contained in there somewhere), we can compute the solution pair (x, y) to the equation in O(k) time.

Now, I'm stuck on this logic because I do not see how storing elements in this data structure helps us or prevents us from having to plug in each of the k elements for X or Y, solve for the other variable, and check if the data structure contains that variable. The only thing I can think of would be somehow keeping two pointers to move along the tree, but that doesn't seem feasible. Could someone explain the reasoning behind this logic?

Upvotes: 0

Views: 234

Answers (1)

John Coleman
John Coleman

Reputation: 52008

Solving linear Diophantine equations (which is what you seem to be thinking of) is trivial and requires nothing more than the extended Euclidian algorithm. On the other hand, the successful resolution of Hilbert's tenth problem implies that there is no algorithm which is able to solve arbitrary Diophantine equations.

There is a vast gap between linear and arbitrary. Perhaps you can focus your question on the type of equation you are interested in.

Upvotes: 1

Related Questions