You're reading: News

P might not be NP, reckons Norbert Blum

Norbert Blum of Universität Bonn has uploaded to the arXiv a preprint of a paper claiming to resolve the problem of whether $\mathrm{P} = \mathrm{NP}$, in the negative.

“Proofs” one way or the other turn up on the arXiv pretty much every day, but this one might actually be correct. At least, it’s not immediately obvious it isn’t.

Here’s the abstract:

Berg and Ulfberg and Amano and Maruoka have used CNF-DNF-approximators to prove exponential lower bounds for the monotone network complexity of the clique function and of Andreev’s function. We show that these approximators can be used to prove the same lower bound for their non-monotone network complexity. This implies $\mathrm{P} \neq \mathrm{NP}$.

John Baez has very quickly put together a post explaining the very basics of Blum’s argument.  Even more briefly, Blum claims to have shown that the best-case complexity of a function solving the clique decision problem is exponential, not polynomial.

Colin Wright reckons that the proof passes all of Scott Aaronson’s immediate ‘sniff tests’ for a claimed proof of a big problem, and his supplementary list for proofs to do with P versus NP. Those help you spot charlatans and Walter Mitty types, rather than looking at the actual mathematical content.

Obviously, none of us are qualified to even offer a hot take on this, so we’ll all have to wait until more experienced sorts have had a good look.

So, watch this space.

(Personally, my money is on this not quite working, purely based on my natural pessimism)

One Response to “P might not be NP, reckons Norbert Blum”

  1. Shecky R

    Since you mention Scott’s “sniff tests” perhaps worth mentioning that Aaronson has already written he expects the “proof” to be “fully refuted by the end of the week” (not because it’s crankery, but just because it’s wrong and he doesn’t “see how this can possibly stand”).
    “Godel’s Lost Letter…” hasn’t weighed in yet, but I’m sure they will soon:
    https://rjlipton.wordpress.com

    Reply

Leave a Reply to Shecky R

  • (will not be published)

$\LaTeX$: You can use LaTeX in your comments. e.g. $ e^{\pi i} $ for inline maths; \[ e^{\pi i} \] for display-mode (on its own line) maths.

XHTML: You can use these tags: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>