My favorite example are a few simple-seeming polynomials with integer solutions. (Equations that we want to solve for integers are called "Diophantene equations".)
Here's one that's genuinely easy:
x^3 + y^3 + z^3 = 29
The solution is x = 1, y = 1, z = 3 (or any permutation thereof).
So how about this one?
x^3 + y^3 + z^3 = 30
Play around a bit.
Not so easy.
But it does have a solution!
Here it is:
x = -283059965
y = -2218888517
z = 2220422932
And what about x^3 + y^3 + z^3 = 33? There is no known solution. It's an open problem!
This is a great visceral demonstration that Diophantene equations are hard: there can exist no algorithm that solves all of them. Diophantene equations, like the Halting Problem, are undecidable.
Here's one that's genuinely easy:
The solution is x = 1, y = 1, z = 3 (or any permutation thereof).So how about this one?
Play around a bit.Not so easy.
But it does have a solution!
Here it is:
And what about x^3 + y^3 + z^3 = 33? There is no known solution. It's an open problem!This is a great visceral demonstration that Diophantene equations are hard: there can exist no algorithm that solves all of them. Diophantene equations, like the Halting Problem, are undecidable.