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)

Review: Factris

Removing four lines at once with an I-piece in Tetris is the most efficient way to score, which creates a tension: on one hand, you want to build high enough to score quickly, but on the other, building too high puts you at risk of ending the game. The balance between the two is exquisite.

I mention that, because I was about to grumble that the corresponding balance in MEI Maths’s new game app thingummy Factris isn’t quite as good – of course it isn’t. Nothing ever will be.

Landon Clay, founder of the Clay Mathematics Institute, has died

The Clay Mathematics Institute, home of the Clay Millennium Maths Prizes, has announced the sad death of its founder, Landon Clay. “Driven by a deep appreciation of the beauty and importance of mathematical ideas”, Clay donated generously to many organisations and projects, including the Institute which he founded in 1998.

Statement on the CMI website, including an addendum from Andrew Wiles

via @LondMathSoc

Maths at the Edinburgh Fringe

Every August a multitude of comedy shows, theatre pieces, interpretive dance performances, musical extravaganzas and spoken word events spring up all over the Edinburgh Fringe. As a busy mathematician (there are infinitely many integers; who has spare time?) I’m sure you’ll appreciate our guide to which of those things are mathematical, or have a tangential (LOL) relationship with mathematics. Please note: none of these are recommendations, as we haven’t seen the shows and mainly have been grepping the word ‘maths’ in online programmes.

News of some significance

You may have heard of the replicability crisis in science, and practices like outcome switching and p-hacking. BuzzFeed reports on a paper that proposes a solution: rather than assign statistical significance at $p=0.05$, change this value to $0.005$.

Sir David Spiegelhalter is quoted saying: “Dealing with the size of the p-value fixes some things. But it’s not dealing with the most important issues.” There’s a lot more in the BuzzFeed article and the full paper.

More information

PsyArXiv preprint: Redefine statistical significance.

BuzzFeed: These People Are Trying To Fix A Huge Problem In Science.