[Solved]: Diophantine equations and P=NP

Problem Detail: 

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?

Asked By : René G

Answered By : David Richerby

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.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/33551

3.2K people like this

 Download Related Notes/Documents