= 27d567bc2d48d9f40e9ccc20ea370b15)
bentarm comments on When does an insight count as evidence? - Less Wrong
You are viewing a comment permalink. View the original post to see all comments and the full post content.
= 783df68a0f980790206b9ea87794c5b6)
Loading…= b715d02e85f7b3b4ae65ca3d3e450868)
Subscribe to RSS Feed
Powered by Reddit
= f037147d6e6c911a85753b9abdedda8d)
You are viewing a comment permalink. View the original post to see all comments and the full post content.
Comments (37)
All mathematicians already agree that P != NP. I'm not sure quite how much more of a consensus you could ask for on an unsolved maths problem.
(see, e.g., Lance Fortnow or Scott Aaronson)
Wouldn't that imply P != NP since otherwise there would be a counterexample?
There is a known concrete algorithm for every NP-complete problem that solves that problem in polynomial time if P=NP:
Generate all algorithms and run algorithm n in 1/2^n fraction of the time, check the result of algorithm n if it stops and output the result if correct.
Nice! More explicitly: if the polynomial-time algorithm is at (constant) index K in our enumeration of all algorithms, we'd need about R*2^K steps of the meta-algorithm to run R steps of the algorithm K. Thus, if the algorithm K is bound by polynomial P(n) in problem size n, it'd take P(n)*2^K steps of the meta-algorithm (polynomial in n, K is a constant) to solve the problem of size n.
No. It could be that there is an algorithm that solves some NP-complete problem in polynomial time, yet there is no proof that it does so. We could even find ourselves in the position of having discovered an algorithm that runs remarkably fast on all instances it's applied to, practically enough to trash public-key cryptography, yet although it is in P we cannot prove it is, or even that it works.
You mean, a substantial majority of sane and brilliant mathematicians. Never abuse a universal quantifier when math is on the line!
You're (all) right, of course, there are several mathematicians who refuse to have an opinion on whether P = NP, and a handful who take the minority view (although of the 8 who did so in Gasarch's survey 'some' admitted they were doing it just to be contrary, that really doesn't leave many who actually believed P=NP).
What this definitively does not mean is that it's rational to assign 50% probability to each side my main point was that there is ample evidence to suggest that P != NP (see the Scott Aaronson post I linked to above) and a strong consensus in the community that P!=NP. To insist that one should assign 50% of one's probability to the possibility that P=NP is just plain wrong. If nothing else, Aaronson's "self-referential" argument should be enough to convince most people here that P is probably a strict subset of NP.
Not all of them.
Just because there are some that disagree doesn't mean we must assign 50% probability to each case.
I wasn't claiming that we must assign 50% probability to each case.