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?

Improve this question
$\endgroup$

1 Answer 1

Reset to default
7
$\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.

Improve this answer
$\endgroup$
7
  • $\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, 2014 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, 2014 at 22:36
  • 3
    $\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, 2014 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, 2014 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, 2014 at 22:59

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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