Grafisomorfialgoritmen er nu rettet.

For kort tid siden skrev jeg, at Helfgott havde fundet en fejl i Babais beregning af tidskompleksiteten for Babais grafisomorfialgoritme. Nu er der igen en kvasipolynomiel grafisomorfialgoritme. Lazslo Babai har rettet algoritmen. Jeg har skrevet om algoritmen. Jeg kan ikke sætte links pænt ind her fra min iPad, men nedenfor er links til det tidligere blogindlæg og nærmere omtale hos Quanta Magazine. Det er ret spændende at kunne følge processen – selvom Babai nok hellere ville have undværet det. Helfgott er nu enig med Babai: Den nye algoritme er kvasipolynomiel.
Tilføjelse 19/1: At et problem er kvasipolynomielt betyder, der findes en løsningsalgoritme, hvis tidskompleksitet $T(n)$ , som eren funktion, der giver antal skridt, algoritmen bruger, som funktion af størrelsen af input (antal knuder plus antal kanter i grafen eksempelvis) , er kvasipolynomiel.
En funktion $T:\mathbb{N}\to \mathbb{R}$ er kvasipolynomiel, hvis den for ethvert $b\in\mathbb{R}_+$ opfylder: Der findes et $n_0$ , så $T(n)\leq b^{\log(n)^c}$ når $n>n_0$ , hvor c er en konstant.
Problemet er subeksponentielt, hvis der findes en algoritme, som løser problemet og hvis tidskompleksitet opfylder:
Der findes for ethvert $b\in\mathbb{R}_+$ et helt tal $n_0$ , så $T(n) \leq b^{n}$ når $n>n_0$
Da den nye (tilrettede) algoritme er kvasipolynomiel, er grafisomorfiproblemet nu kvasipolynomielt.

Helfgott finder fejl i Babais artikel om grafisomorfiproblemet

https://www.quantamagazine.org/20170114-graph-isomorphism-babai-fix/