Extensive discussion a few hours ago
P = NP [pdf]
11–19 of 19 posts
Re: P = NP [pdf]
#12Well 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!
What are the implications?
Re: P = NP [pdf]
#13A 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
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
Re: P = NP [pdf]
#14The 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.
There was also an entire (unrelated) film based on the same concept, called Traveling Salesman.
Re: P = NP [pdf]
#15Well 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!
What are the implications?
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.
http://en.wikipedia.org/wiki/P_versus_NP_problem#Consequence... has better details than I can give.
Re: P = NP [pdf]
#16Re: P = NP [pdf]
#17Earlier quoted context omitted.
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. Ah - I see now. Gotcha.
Where did you see? I looked at revisions and noticed that the recent revisions were in 2013.
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.
Re: P = NP [pdf]
#18This 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?
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.
No, it's well known that nobody has yet resolved P vs NP.
Re: P = NP [pdf]
#19The 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.