›
This forum is in permanent archive mode. Our new active community can be found here.

P != NP...maybe

Dr. TimoDr. Timo
edited August 2010 in Everything Else
This is my thing of the day, but I think it deserves a thread of it's own!

P != NP

If proven correct (and usually there are only minor flaws found in the peer review), this spells good news for crypto and even better news for quantum computing research funding.

Comments

  • AprecheApreche
    You're a cuople days late. Apparently someone has found a flaw in the paper. I am not smart enough to understand anything they are talking about. Perhaps someone can translate.

    http://rjlipton.wordpress.com/2010/08/09/issues-in-the-proof-that-p%E2%89%A0np/#comment-4712
  • Dr. TimoDr. Timo
    I knew about this right when the paper got out, I waited however for the story to be in a credible publication. Once criticism of this proof is published in Nature or Science, I'll be less optimistic.
  • AprecheApreche
    edited August 2010
    I knew about this right when the paper got out, I waited however for the story to be in a credible publication. Once criticism of this proof is published in Nature or Science, I'll be less optimistic.
    That seems reasonable to me. A comment on a blog is pretty far away from Reason.
    Post edited by Apreche on
  • AndrewAndrew
    I edited the title, the inner theoretician in me couldn't stand it as originally posted ~_^
  • AndrewAndrew
    Here is a working wiki on the topic that covers the paper's work and possible limitations.
  • AprecheApreche
    edited August 2010
    If someone wrote a book that a person like me could understand that explained all of these mathematical terms and concepts in plain English, I would buy it.

    Also, if this guy is right, then he should mail his money to the Russian guy who refused the prize. For awesomeness.
    Post edited by Apreche on
  • AndrewAndrew
    If someone wrote a book that a person like me could understand that explained all of these mathematical terms and concepts in plain English, I would buy it.
    How to read Math
  • okeefeokeefe
    edited August 2010
    If Vinay Deolalikar is awarded the $1,000,000 Clay Millennium Prize for his proof of P≠NP, then I, Scott Aaronson, will personally supplement his prize by the amount of $200,000.
    The updates that have since appeared include more possible holes.
    Post edited by okeefe on
  • Dr. TimoDr. Timo
    edited August 2010
    The updates that have since appears include more possible holes.
    This is very normal in mathematical proofs, e.g. the original proof of Fermat's last problem had several errors that needed to be corrected. Perelman's case, in which a monumental proof is correct at the get go, is the exception.

    One has to realize that mathematical notation is very dense and that a proof 100 pages long has at least that many intermediary steps, invocations of lemma's, sub-results, etc. etc.. Other persons reading the proof cursorily can find several "wonky" steps or holes in the proof without this being a problem because either a) the procedure of that step can be easily improved, or b) the reader didn't entirely understand the authors intent at that step (and the wonkyness is taken care of elsewhere in the paper in a non obvious way).

    Think of a mathematical proof as a computer program that you can only check for correctness by reading the code. No compiling and running to see if it crashes. Take the Poincare conjecture that Perelman solved; the proof was some 68 pages all together and it took two separate ~500 page reports to validate the proof.

    All this being said, it is of course possible that the author made an easy to spot fatal error, but until such error(s) are published or the author retracts his paper, I'm cheering for the guy. Seeing problems of this caliber fall is very exciting to me, and at the rate they are going I may very well live to see the list depleted.
    Post edited by Dr. Timo on
  • Alex LeavittAlex Leavitt
    I work at Microsoft Research (New England), and all of the mathematicians here completely dismissed the report immediately after it came out. 0_o''
  • Dr. TimoDr. Timo
    Sigh, the way this paper has been received by "the web" illustrates one of my pet peeves when it comes to science reporting. Namely, that the 24h news cycle / blogosphere / twitterbook scene is a ADHD raccoon in an Arnold's trashcan after closing time that has just swallowed a crack pipe, and science is slow and methodical.

    From the above link (emphasis mine)
    Before the age of Twitter, Facebook and social news aggregation , draft research papers on something as complex as P ≠ NP would have gone through a rigorous academic process, which would focus on whether the proof strategy is correct, and whether the perceived gaps are easily remedied.
    The discrepancy between the attention span of the media and the time it takes to scientifically vet something is why we have "electricity allergy", power lines that cause cancer, cell phones that do the same, and vaccines that cause autism.
  • AndrewAndrew
    image
  • RymRym
    There's a tiny chance that P==NP.

    Granted, P==NP is no match for 8==D.
  • Josh BytesJosh Bytes
    I see what you did there.
Sign In or Register to comment.