7 ms·
P≠NP proof update
- amichail 16y agoGiven the ad hoc way in which this peer review is being done on the web, perhaps there's a startup opportunity here...
- lrm242 16y agoI'm not sure why this is getting down voted. There is an opportunity here to build a web application to help the peer review process. Whether the academic community wants such a thing is beyond me, but the observation is perfectly valid.
- nl 16y agoThe whole math community on the web thing mostly started when Wordpress added support for LaTex (which let them use formula). There have been some attempts to use Wikis for the same process, but from casual observation they seem to keep returning to using blogs. There is MathOverflow though: http://mathoverflow.net/ http://mathoverflow.net/
- robryan 16y agoI think on most research the current pace of the informal peer reviews and discussion is unusual and unsustainable. On most things I think it would be unnecessary.
- k3dz 16y agoi think the deluge of comments we're seeing from the math community is because the paper claims to solve one of the toughest problems out there. this wouldn't scale to findings of a lesser importance
- blantonl 16y agoWatching this process unfold has been extremely entertaining - solely from the perspective of watching how highly scientific / mathematical communities resolve these types of occurrences. There is a LOT of tip-toeing going on, and it seems there is a very established, methodical, and specific process that is followed by those in these communities. You have to wonder if some of these mannerisms could (should?) apply to open source development :) I've attended college, but I'm not a graduate and never really experienced any of the higher-level mathematical courses, so this proof (and discussions thereof) are completely greek to me. But I can certainly tell that based on the discussions and claims the researcher dropped an A-bomb and the math and CS communities are abuzz. For those that are in my situation - is there any layman's summarization that describes what this proof really means to the computer science community? Even the Wikipedia entry has me lost at the second paragraph.
- barrkel 16y agoTo an extreme approximation, problems in P are easy and problems in NP are hard. This is important for e.g. cryptography: its security relies on hard problems staying hard. If it were found that P = NP, it would mean that we would have an easy solution to hard problems. On the other hand, if P != NP, then we could rest assured that the hard problems will stay that way.
- carbocation 16y agoI think that is a bit too extreme of an approximation. What if someone proved that all NP problems could be solved in n * 1000^1000 time? That is in polynomial time (linear, in fact), but completely intractable. Edit: removed Big O notation, since my point here is actually that the constant might be so large that you'd never get to a point where the limiting case would matter. Sorry to set off a firestorm.
- barrkel 16y agoI actually removed that point from my comment - that problems in P may be intractable, so it may be academic anyhow. But a way of turning NP-complete problems into problems in P (i.e. P = NP) would hopefully mean that intractable NP problems would be tractable P problems, even if only for relatively small values of n.
- carbocation 16y agoHopefully true, I agree.
- jules 16y agoO(n * c) = O(n), the whole point of the O-notation.
- carbocation 16y agoNo. It's only asymptotically equivalent. If the constant is enormous relative to some absolute measure (say, the number of transistors on earth) then O-notation doesn't meaningfully help you.