Slashdot Mirror

← Back to Stories (view on slashdot.org)

New Work Suggests That P Is Not Equal To NP (arxiv.org)

Posted by msmash on from the this-changes-everything dept.

New submitter cccc828 writes: In a new paper Norbert Blum tackles the P=NP question and finds them to be not equal. While this is exciting news (for theoretical computer scientists at least), remember that there is a long list of findings pointing either way.

3 of 147 comments (clear)

  1. "While this is exciting news" by Stormy+Dragon · · Score: 3, Informative

    Since P != NP is the expected answer, is this news really that exciting? Evidence that P = NP is the one that would actually be exciting, since it would suggest the existence of an unknown algorithm that handles certain problems far more efficiently than the currently known alternatives.

    1. Re:"While this is exciting news" by Stormy+Dragon · · Score: 5, Informative

      or one is a subset of the other

      P is already known to be a subset of NP. The question is whether it is a proper subset (P != NP) or not (P = NP).

      Evidence that P = NP means all cryptography is doomed to fail.

      Exciting news is obviously not always good news.

  2. Hold your horses by l2718 · · Score: 4, Informative

    This is merely a preprint, not a published paper. In other words, this has not been referred – subjected to regular scientific scrutiny.

    Preprints are of great interest to researchers in the field -- they give them quick access to recent results before the slower process of scientific verification takes place. But preprints are not published papers (even those are not all correct!) – they aren't really useful to the general public. Especially in the case of major open problems like P=NP, such extraordinary claims require extraordinary verification, and this has yet to take place.

    The submission headline here is very misleading, as is the summary. Either this preprint is correct (extremely unlikely), and then it definitely shows that P!=NP, or the preprint if wrong (almost surely the case), at which point it's not clear that it contains enough correct and deep results to actually suggest anything about whether P=NP or not. A much better headline would have been "new arXiv preprint purports to prove that P!=NP", and a better summary would have been

    A recent arXiv preprint by Norbert Blum of the University of Bonn claims to show that P!=NP. This work has not been vetted by the general community and (as with every other claim of this type) is generally assumed to be incorrect. Readers who are not experts in complexity theory are advised to ignore this preprint until experts have had time to examine this work and its implications.