1
$\begingroup$

I'm sorry if this is a newbie question but I'm not sure how to approach it.

I have a problem that I want to solve(by creating an algo) and I'm pretty sure its a Diophantine equation, but I'm not sure how to solve if there's more than a few variables. I created a script that solves for 3 variables(basically by brute force), I'm wondering if there's anything out there to learn better?

(fyi I'm very interested in math and am willing to learn but my math background is weak so sorry if I'm not asking correctly).

  • 0
    thanks for the reply Thomas. I'm not 100% sure because my math background is very weak(since highschool no math and that was over 10 years ago..but its never too late to learn!). I posted this question a few months back http://math.stackexchange.com/questions/27732/what-type-of-math-is-this and now I'm ready to dedicate myself to this 100%. I looked around and many examples were only with 2 or 3 variables..I'm trying to figure out a way to do this with thousands of variables.2011-06-05

1 Answers 1

3

One can also brute force with $n$ variables. But it is known that there is no general algorithm that will determine whether a Diophantine equation has a solution.

This beautiful and important result solves (in the negative) what is called Hilbert's 10th Problem.

In particular, there is no general algorithm that will determine, in advance, whether a brute force search will terminate.

Of course there are algorithms for particular classes of Diophantine equations, for example (easily) linear ones and (less easily) quadratic ones.

  • 0
    @Lostsoul: I looked at the stuff you added to your post, including the link. If things have not changed, you are looking at linear Diophantine equations, for which there is pretty complete theory and good algorithms. So the general undecidability result I replied with would be irrelevant. But interesting!2011-06-05