Because if it were otherwise—if verifying a solution were of the same order of computational difficulty of finding it -- it would be a lot harder to account for my observations than if it weren’t so.
For example, verifying a proof would be of similar difficulty to finding the proof, which would mean nature would stumble upon representations isomorphic to either with similar probability, which we do not see.
The possibility that P = NP but with a “large polynomial degree” or constant is too ridiculous to be taken seriously; the algorithmic complexity of the set of NP-complete problems does not permit a shortcut that characterizes the entire set in a way that would allow such a solution to exist.
I can’t present a formal proof, but I have sufficient reason to predicate future actions on P ≠ NP, for the same reason I have sufficient reason to predicate future actions on any belief I hold, including beliefs about the provability or truth of mathematical theorems.
Most human mathematicians think along similar lines. It will still be a big deal when P ≠ NP is proven, if for no other reason that it pays a million dollars. That’s a lot of paperclips.
The possibility that P = NP but with a “large polynomial degree” or constant is too ridiculous to be taken seriously; the algorithmic complexity of the set of NP-complete problems does not permit a shortcut that characterizes the entire set in a way that would allow such a solution to exist.
Because if it were otherwise—if verifying a solution were of the same order of computational difficulty of finding it -- it would be a lot harder to account for my observations than if it weren’t so.
For example, verifying a proof would be of similar difficulty to finding the proof, which would mean nature would stumble upon representations isomorphic to either with similar probability, which we do not see.
The possibility that P = NP but with a “large polynomial degree” or constant is too ridiculous to be taken seriously; the algorithmic complexity of the set of NP-complete problems does not permit a shortcut that characterizes the entire set in a way that would allow such a solution to exist.
I can’t present a formal proof, but I have sufficient reason to predicate future actions on P ≠ NP, for the same reason I have sufficient reason to predicate future actions on any belief I hold, including beliefs about the provability or truth of mathematical theorems.
Most human mathematicians think along similar lines. It will still be a big deal when P ≠ NP is proven, if for no other reason that it pays a million dollars. That’s a lot of paperclips.
Let me know if you think you can solve any of these! http://www.claymath.org/millennium/
Would you elaborate.
Under the right conditions, yes.