I 2015 troede vi, der var nyt om kompleksiteten af grafisomorfiproblemet. Det skrev jeg om på bloggen (med undertitlen “rygters bureau” – man skulle tro, jeg havde en krystalkugle).
Nyheden var dengang, at Laszlo Babai havde lavet en ny algoritme til at afgøre, om to grafer er isomorfe og at tidskompleksiteten for den nye algoritme er 
Nu har Harald Helfgott, som er berømt (i visse kredse…) for at have bevist den svage Goldbachformodning, fundet en fejl i Babais artikel. Det viser sig, at kompleksiteten af algoritmen er 
Helfgott skriver på sin blog, at han fandt fejlen, da han forberedte sig til at holde Bourbakiforedrag om Babais resultat. I den forbindelse skal man skrive beviset ud (eller op eller ned), så matematikere fra andre områder også kan læse det – og der var altså noget, der ikke stemte. Algoritmen virker, men analysen af tidskompleksiteten er forkert. Helfgott skriver, man måske kan forbedre algoritmen. I hvert fald er det klart, hvor problemet er.
Babai skriver på sin hjemmeside om det nye.
The technical content of the paper remains virtually unchanged. The previous analysis breaks down for one of the recursive steps of the combinatorial “Split-or-Johnson” procedure; but the “Split-or-Johnson” theorem remains valid with the updated timing analysis. All other results are unaffected. I am working on an updated arXiv posting (with a different title) that will also improve the presentation, following comments from several colleagues.
Og så er han en smule sarkastisk: I apologize to those who were drawn to my lectures on this subject solely because of the quasipolynomial claim, prematurely magnified on the internet in spite of my disclaimers. I believe those looking for an interesting combination of group theory, combinatorics, and algorithms need not feel disappointed.
“Prematurely magnified on the internet” – jow jow, bloggen her var ikke den eneste, der løb med en halv vind. Undskyld 🙂 Får man mon tilgivelse, når man har skrevet “rygters bureau”?