> It also doesn't really matter if a statement is provable in theory or not. Whether or not it's possible to prove that P?=NP, it is either true or it's false and it has always been either true or false, and one of those two programs is correct.
This is a pretty philosophically extremist statement (relying on a hardcore version of Platonism) and with my handle I can’t just let it stand unchallenged. :)
I’m actually somewhat more sympathetic to excluded middle for P?=NP than for some other statements, so let’s start elsewhere. I don’t think it’s at all obvious that the continuum hypothesis is, and always has been, either true or false. We know it’s independent of ZFC, of course, and there are sensible “extra” axioms that would resolve it in opposite directions (e.g. V=L vs. MM). In order to believe that there’s a fact of the matter you need to posit a very well-populated Platonic realm, despite not needing that kind of philosophical commitment to do mathematics.
Well, maybe P?=NP is just simpler than CH. It probably is! But you can imagine a case where it isn’t; e.g. if there exists an algorithm for 3-SAT (call it Algorithm A) which can be proved to be asymptotically optimal, and which runs in O(n^10^100) time if !CH, and exponential time if CH. Then the P?=NP question would be equivalent to CH, and you should have the same beliefs about its truth value. If you’re like me, that means you’re skeptical that it has a well-defined truth value “for all time” at all.
In that case, either of "return false" or "return true" are valid computable functions depending on the domain you're operating in (with CH or without it).
It's the same essentially as a function that returns true if any two lines will eventually intersect. The correct answer depends on whether you're in curved space or not. That the correct answer depends on the domain or axioms doesn't make it non computable.
There's just no case where a constant function isn't computable in the technical sense.
This is a pretty philosophically extremist statement (relying on a hardcore version of Platonism) and with my handle I can’t just let it stand unchallenged. :)
I’m actually somewhat more sympathetic to excluded middle for P?=NP than for some other statements, so let’s start elsewhere. I don’t think it’s at all obvious that the continuum hypothesis is, and always has been, either true or false. We know it’s independent of ZFC, of course, and there are sensible “extra” axioms that would resolve it in opposite directions (e.g. V=L vs. MM). In order to believe that there’s a fact of the matter you need to posit a very well-populated Platonic realm, despite not needing that kind of philosophical commitment to do mathematics.
Well, maybe P?=NP is just simpler than CH. It probably is! But you can imagine a case where it isn’t; e.g. if there exists an algorithm for 3-SAT (call it Algorithm A) which can be proved to be asymptotically optimal, and which runs in O(n^10^100) time if !CH, and exponential time if CH. Then the P?=NP question would be equivalent to CH, and you should have the same beliefs about its truth value. If you’re like me, that means you’re skeptical that it has a well-defined truth value “for all time” at all.