Vorig jaar januari schreven we in het Journaal over een doorbraak in het berucht hardnekkige probleem om te bepalen of twee grafen isomorf zijn. Een ‘graaf ’ is een verzameling punten met verbindingen ertussen. En ‘isomorf ’ betekent in feite ‘hetzelfde’. De twee afgebeelde grafen zijn isomorf.

Voor grote grafen kan het erg moeilijk zijn om te zien of ze isomorf zijn. Eind 2015 presenteerde László Babai (universiteit van Chicago) een algoritme dat voor twee gegeven grafen kan berekenen of ze isomorf zijn. Dat algoritme was flink sneller dan de algoritmen die tot dan toe voor dit probleem bekend waren. Het efficiëntste algoritme vóór Babais doorbraak was van Eugene Luks en stamt uit 1983. Babais algoritme werd gezien als een van de grootste doorbraken op dit gebied in tien jaar.

Maar begin vorige maand kondigde Harald Helfgott (universiteit van G.ttingen) aan dat hij een fout in Babais algoritme had ontdekt. Hij had Babais werk uitgebreid bestudeerd en kwam er na maanden achter dat het algoritme een hiaat bevatte. Babai erkende de fout, maar wist die spoedig te repareren. Binnen enkele dagen kwam hij met een nieuwe versie. Nu maar hopen dat die foutloos blijkt.