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?
Every problem in NP is decidable. Since determining whether Diophantine equations have solutions is undecidable, it cannot be in NP.  Therefore, although the solution to the equation is a certificate, the size of this certificate is not bounded by any polynomial in the size of the input.