Slashdot Mirror

← Back to Stories (view on slashdot.org)

How the Web Rallied To Review the P != NP Claim

Posted by Soulskill on from the peer-to-peer-review dept.

An anonymous reader writes "Remember, about a month ago, when a researcher claimed he had a proof that P != NP? Well, the proof hasn't held up. But blogs and news sites helped spur a massive, open, collaborative effort on the Internet to understand the paper and to see if its ideas could be extended. This article explains what happened, how the proof was supposed to work, and why it failed."

8 of 160 comments (clear)

  1. The greatest gift by Jedi+Alec · · Score: 5, Insightful

    No matter the flaws with his paper, this guy has certainly managed to inspire a whole lot of people to delve into a subject and collaborate on it.

    Those who think deep thoughts are precious. Those who manage to inspire thousands of others to do so...

    --

    People replying to my sig annoy me. That's why I change it all the time.
    1. Re:The greatest gift by phaunt · · Score: 5, Informative

      That's exactly what he did. He mailed it to a small group of experts and asked them for their comments. Some of them sent it on, commenting: "hey, this looks like a legit attempt", and before Vinay knew it, his article was on the web.

  2. Damn... by PmanAce · · Score: 5, Funny

    I guess I will never profit from my proof I posted a while ago since his didn't hold up:

    Step #1: Wait for him to prove and confirm P!=NP
    Step #2: Solve for N:
    So P!=NP,
    therefore P!/P=N,
    thus the Ps cancel and we are left with N=!.
    Step #3: ???
    Step #4: Profit!

    --
    Tired of my customary (Score:1)
  3. Re:A simpler proof? Please? by rubycodez · · Score: 5, Insightful

    there should be a simpler way to go about showing that P != NP

    that simpler way would only exist if P = NP

  4. OT: sig comment by beschra · · Score: 5, Funny

    People replying to my sig annoy me. That's why I change it all the time.

    Time to change again.

    --
    It is unwise to ascribe motive
  5. Re:A simpler proof? Please? by JoshuaZ · · Score: 5, Informative

    While the parent has been modified "funny" it really should be modified as informative or insightful. Scott Aaronson for example has discussed this issue in detail. If P=NP then we expect proofs in general in some sense to be easy but if P !=NP then in some sense proofs are difficult. (More rigorously speaking, given a well-behaved axiomatic system A, questions of the form "Is there a proof of statement s from axioms in A with the proof length at most k?" are NP-hard and for reasonable enough systems in fact NP-complete. So if P=NP proving that in some rough sense should be easy. But if P != NP then we expect proofs to be difficult. This is one of the reasons many experts actually believe P !=NP.

  6. Re:Nerd Superbowl by JamesP · · Score: 5, Funny

    Yeah, but nobody scored...

    --
    how long until /. fixes commenting on Chrome?
  7. slashdot has confusing hyperlinks in its summaries by ljw1004 · · Score: 5, Interesting

    This summary had three hyperlinks:

    1. "claimed he had a proof"
    2. "hasn't held up"
    3. "spur a massive effort"

    It was missing the only IMPORTANT hyperlink:

    4. "this article". --- The slashdot submission was about an article. I'd like to read the article. I'd like a hyperlink which unambiguously takes me to the article. As it was, I didn't know which of the hyperlinks would take me to the article.

    1. "claimed he had a proof" -- did this hyperlink take me to his claim? No: it took me to a online collaborative discussion of his claim (i.e. the original slashdot article).

    2. "didn't hold up" -- did this hyperlink take me to the announcement that it didn't hold up? No: it took me to a slashdot article that maybe had a link to the statement about how it didn't hold up.

    3. "spur a massive effort" -- did this hyperlink take me to that effort? Or did it take me to the spur in question? No: it took me to a REVIEW of that effort.

    The hyperlinks in Slashdot summaries are always confusing.