Slashdot Mirror

← Back to Stories (view on slashdot.org)

Possible Issues With the P != NP Proof

Posted by Soulskill on from the intuitively-obvious-to-the-most-casual-observer dept.

An anonymous reader writes "We previously discussed news that Vinay Deolalikar, a Principal Research Scientist at HP Labs, wrote a paper that claimed to prove P is not equal to NP. Dick Lipton, a Professor of Computer Science at Georgia Tech, analyzed the idea of the proof on his blog. In a recent post, he explains that there have been many serious objections raised about the proof. The post summarizes the issues that need to be answered in any subsequent development, and additional concerns are raised in the comment section."

6 of 147 comments (clear)

  1. I for one by Chuck+Chunder · · Score: 5, Funny

    feel very very stupid after reading that.

    --
    Boffoonery - downloadable Comedy Benefit for Bletchley Park
  2. Publication Bias by mSparks43 · · Score: 5, Funny

    Like I said last time. The trouble is, every time someone proves P=NP, the NSA arranges them a little accident.

    1. Re:Publication Bias by martin-boundary · · Score: 4, Funny

      You can't be sure of that. The NSA can only "accident" all those who prove P=NP if the proof verification algorithm requires polynomial time to complete.

  3. Re:Yes, they've tried that by nomoreunusednickname · · Score: 5, Funny

    I have discovered a truly marvelous proof that P!=NP. But this comment is too deterministic to contain it.

  4. Re:Current Status by Affenkopf · · Score: 5, Funny

    The paper was preliminary to begin with. It is currently withdrawn in order to fix minor typos

    Minor typos like a ! that m,ade it into the paper by accident.

  5. Re:Hard core by tehcyder · · Score: 5, Funny

    "Formal Language Theory" - an undergrad course at my university that dealt with Finite State Automata, Touring Machines, Computability Theory, Complexity Theory,

    How cool was that, I assume it was to give you a theoretical basis for the use of car analogies.

    --
    To have a right to do a thing is not at all the same as to be right in doing it