P = NP [pdf]

#1

Post by gabceb » Wed, Dec 04, 2013, 11:00 PM UTC

Re: P = NP [pdf]

#2

Post by Schwolop » Wed, Dec 04, 2013, 11:04 PM UTC

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!

Re: P = NP [pdf]

#3

Post by madcaptenor » Wed, Dec 04, 2013, 11:07 PM UTC

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?

Re: P = NP [pdf]

#4

Post by Sniffnoy » Wed, Dec 04, 2013, 11:13 PM UTC

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

Re: P = NP [pdf]

#5

Post by Schwolop » Wed, Dec 04, 2013, 11:14 PM UTC

madcaptenor wrote: post #3

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.

Re: P = NP [pdf]

#6

Post by rinon » Wed, Dec 04, 2013, 11:16 PM UTC

madcaptenor wrote: post #3

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?

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.

Re: P = NP [pdf]

#7

Post by Osiris » Wed, Dec 04, 2013, 11:16 PM UTC

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.

Re: P = NP [pdf]

#8

Post by Ov3rload » Wed, Dec 04, 2013, 11:19 PM UTC

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.

Re: P = NP [pdf]

#9

Post by [deleted] » Wed, Dec 04, 2013, 11:20 PM UTC

[deleted]

Re: P = NP [pdf]

#10

Post by sukuriant » Wed, Dec 04, 2013, 11:21 PM UTC

Schwolop wrote: post #5

madcaptenor wrote: post #3

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.