Kevin comments on Open Thread, August 2010 - Less Wrong

4 Post author: NancyLebovitz 01 August 2010 01:27PM

You are viewing a comment permalink. View the original post to see all comments and the full post content.

Comments (676)

You are viewing a single comment's thread. Show more comments above.

Comment author: Kevin 08 August 2010 10:51:02PM 1 point [-]

How do you know you know?

Comment author: JoshuaZ 09 August 2010 12:04:49AM *  2 points [-]

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.

Comment author: Sniffnoy 09 August 2010 05:17:17AM 1 point [-]

URL is repeated twice in link?

Comment author: JoshuaZ 09 August 2010 01:45:33PM 0 points [-]

Thanks, fixed.

Comment author: Clippy 08 August 2010 11:14:59PM *  1 point [-]

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.

Comment author: Kevin 08 August 2010 11:50:09PM 1 point [-]

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/

Comment author: [deleted] 09 August 2010 01:32:01AM 0 points [-]

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.

Would you elaborate.