You're reading: Posts Tagged: almost a proof

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)

László Babai reckons he can decide if two graphs are isomorphic in quasipolynomial time

László Babai in Chicago. Photo by Gabe Gaster, used with permission.

We’ve been slow to cover this, but if this week has taught us anything, it’s that taking your time over Important Maths News is always a good idea.

A couple of weeks ago, rumours started circulating around the cooler parts of the internet that László “Laci” Babai had come up with an algorithm to decide if two graphs are isomorphic in quasipolynomial time. A trio of mathematicians including Tim Gowers were on BBC Radio 4’s In Our Time discussing P vs NP while these rumours were circulating and made a big impression on Melvyn Bragg as they talked so excitedly about the prospect of something big being announced.

If Babai had done what the rumours were saying, this would be a huge advance – graph isomorphism is known to be an NP problem, so each step closer to a polynomial-time algorithm raises the P=NP excite-o-meter another notch.

So what happened to the abc conjecture and Navier-Stokes?

Has there been any progress on verifying the proof of the abc conjecture or the solution to the Navier-Stokes equations? It’s been eerily quiet. I’m never going to come close to understanding any of those things, so I’ve been eagerly awaiting news that they’ve been either accepted or rejected.

abc: the story so far

You should take some time to read this very well-written piece about Shin Mochizuki’s claimed proof of the abc conjecture: “The Paradox of the Proof”, by Caroline Chen.

It covers the story from all angles: a biog of Mochizuki, a clear, non-nonsense description of the conjecture, the tale of the mathematical community’s attempts to understand it, and some insightful rumination on the nature of proof.

via Marcus du Sautoy on Twitter, among others

(TL;DR – still nobody knows whether the proof is correct or not)

The invariant subspace problem is still a problem

Well, yesterday they announced at the blog Café Matemático that there was a problem with their proof:

The invariant subspace problem is solved for Hilbert spaces?

Update 05/02/2013: Cowen and Gallardo say that a problem has been found in their proof and they no longer claim an answer to the invariant subspace problem.

At the congress of la Real Sociedad Matemática Española yesterday, Eva Gallarda and Carl Cowen presented an affirmative answer to the invariant subspace problem on separable Hilbert spaces. While it isn’t a Millennium Prize problem, it’s one of the big open problems in maths. As far as I can tell, it hasn’t been through any formal peer review yet, but they’re serious people and you’ve got to be quite sure about this kind of thing before announcing it at such a high-profile event.