1
$\begingroup$

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?

$\endgroup$
6
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ The certificate is precisely the size of the input; for example for the equation x^2 + y^2 = 2 one certificate would be (1,1) which is the same as the length of the left side of the equals: the certificate is the sane length as the number of variables. $\endgroup$ – Elliot Gorokhovsky Nov 26 '14 at 22:35
  • $\begingroup$ 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). $\endgroup$ – David Richerby Nov 26 '14 at 22:36
  • 2
    $\begingroup$ The size of a certificate isn't just the number of numbers in it, the size of the numbers themselves also contributes towards the size of the certificate. $\endgroup$ – Tom van der Zanden Nov 26 '14 at 22:43
  • $\begingroup$ Ya sorry that was a mistake but can you explain in more detail why the certificate is unbounded? $\endgroup$ – Elliot Gorokhovsky Nov 26 '14 at 22:47
  • 1
    $\begingroup$ The size of the certificate is, as @TomvanderZanden says, the number of bits required to write out the answer. If that were bounded by a polynomial, the problem would be in NP but we know it's not in NP (because it's undecidable) so there can't be a polynomial bound. I don't, off the top of my head, know any examples of short Diophantine equations with large solutions and I'm not familiar with the undecidability proof so I can't give an answer that gives a more intuitive explanation than "Because it's undecidable." $\endgroup$ – David Richerby Nov 26 '14 at 22:59

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.