4 ms·
P = NP [pdf]
- Schwolop 13y agoWell I for one freely admit I can't understand a word of it. But I do appreciate the implications if it's true, and look forward to more readable analysis by others more qualified than myself!
- elwell 13y agoWhat are the implications?
- Schwolop 13y agoAmongst other things, that public key cryptography is crackable in polynomial time, rendering it effectively useless if a generalisable algorithm (such as presented in the paper) is able to convert a non-polynomial time algorithm into a polynomial time one. http://en.wikipedia.org/wiki/P_versus_NP_problem#Consequences_of_the_resolution_of_the_problem http://en.wikipedia.org/wiki/P_versus_NP_problem#Consequence... has better details than I can give.
- mek 13y agoAmongst other things, Bitcoin mining
- madcaptenor 13y agoThis is from August of 2012. If there were actually a proof of P = NP posted on the arXiv, wouldn't we have heard about it by now?
- Schwolop 13y agoWhere did you see that it's from August 2012? I recall a claim in August 2010 by Vinay Deolalikar of the opposing view, but haven't seen much public attention since. Ah - I see now. Gotcha.
- sukuriant 13y agoWhere did you see? I looked at revisions and noticed that the recent revisions were in 2013.
- madcaptenor 13y agoThe original version is from August 2012. I didn't look at the revision history. In any case, having that long of a revision history (31 versions!) also seems like a red flag.
- rinon 13y agoThere's been plenty of proposed proofs on both sides, however there has been little agreement on whether these proofs are indeed correct. See http://www.win.tue.nl/~gwoegi/P-versus-NP.htm http://www.win.tue.nl/~gwoegi/P-versus-NP.htm for more links.
- j2kun 13y agoNo, it's well known that nobody has yet resolved P vs NP.
- Sniffnoy 13y agoA note -- when linking to arXiv, please link to the abstract[1], not directly to the PDF. The abstract has other information about the paper, and one can see different versions of the paper, and of course one can click through to the actual paper. Going the other way requires manually editing the URL. [1]http://arxiv.org/abs/1208.0954 http://arxiv.org/abs/1208.0954
- alepper 13y agoPresumably it was done this way to avoid the duplicate filter spotting that the same article was submitted under the other URL 11 hours ago: https://news.ycombinator.com/item?id=6846228 https://news.ycombinator.com/item?id=6846228
- Osiris 13y agoThe TV show Elementary did an episode in which someone solved N = NP and then used the solution to break any encryption they wanted. It all seemed a little far fetched to me.
- vezzy-fnord 13y agoThere was also an entire (unrelated) film based on the same concept, called Traveling Salesman.
- j2kun 13y agoI think you mean P = NP. And if a certain kind of proof of P = NP is found then yes, it would actually mean that you can break any encryption that exists today. That's why it lends itself so nicely to TV drama.
- Ov3rload 13y agoThere are many proofs, you can find some of them here: http://www.win.tue.nl/~gwoegi/P-versus-NP.htm http://www.win.tue.nl/~gwoegi/P-versus-NP.htm Like all famous problems, P vs NP attracts a great number of people, mostly amateurs, that want to try to solve it. Most of those proofs are not peer reviewed, all of them are probably wrong.
- deleted 13y ago[deleted]
- Anon84 13y agoExtensive discussion a few hours ago https://news.ycombinator.com/item?id=6846228 https://news.ycombinator.com/item?id=6846228