There’s a very good summary by Scott Aaronson describing why we believe that P is very likely to be not equal to NP. However, Clippy’s confidence seems unjustified. In particular, there was a poll a few years ago that showed that a majority of computer scientists believe that P=NP but a substantial fraction do not. (The link was here but seems to be not functioning at the moment (according to umd.edu’s main page today they have a scheduled outage of most Web services for maintenance so I’ll check again later. I don’t remember the exact numbers so I can’t cite them right now)).
This isn’t precisely my area, but speaking as a mathematician whose work touches on complexity issues, I’d estimate around a 1⁄100 chance that P=NP.
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.
How do you know you know?
There’s a very good summary by Scott Aaronson describing why we believe that P is very likely to be not equal to NP. However, Clippy’s confidence seems unjustified. In particular, there was a poll a few years ago that showed that a majority of computer scientists believe that P=NP but a substantial fraction do not. (The link was here but seems to be not functioning at the moment (according to umd.edu’s main page today they have a scheduled outage of most Web services for maintenance so I’ll check again later. I don’t remember the exact numbers so I can’t cite them right now)).
This isn’t precisely my area, but speaking as a mathematician whose work touches on complexity issues, I’d estimate around a 1⁄100 chance that P=NP.
URL is repeated twice in link?
Thanks, fixed.
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.