You're reading: Posts Tagged: almost a proof

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

Recently we reported that Eva Gallarda and Carl Cowen had announced they had a proof of the invariant subspace conjecture for Hilbert spaces.

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.