Well 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!
Amongst 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.
Where 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.
The 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.
There'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 for more links.
A 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.
Presumably 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
The 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.
I 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.
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.
18 comments
[ 3.7 ms ] story [ 52.3 ms ] threadhttp://en.wikipedia.org/wiki/P_versus_NP_problem#Consequence... has better details than I can give.
Ah - I see now. Gotcha.
[1]http://arxiv.org/abs/1208.0954
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.
https://news.ycombinator.com/item?id=6846228