# Diophantine equations and P=NP

It was proven that the problem of determining whether a given Diophantine equation has a solution is undecidable (and therefore has no polynomial time algorithm). But we can check proof certificates (that is, solutions to the equation) in linear time by plugging in our solution and evaluating. So the problem is in NP. Why does this not imply P $\neq$ NP?

• One instance having a short certificate doesn't mean they all do (also, $1^2 + 2^2\neq 2$ but that's beside the point). – David Richerby Nov 26 '14 at 22:36