P = NP [pdf] | Hacker News Reader

P = NP [pdf]

arxiv.org

27 pointsgabceb16 comments

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.

[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

This 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?

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.

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.

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.

There was also an entire (unrelated) film based on the same concept, called Traveling Salesman.

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.

Extensive discussion a few hours ago

https://news.ycombinator.com/item?id=6846228

There are many proofs, you can find some of them here:

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.

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!

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.

Reply on news.ycombinator.com