Le problème d'isomorphisme des graphes moins complexe qu'on ne le pensait

Le problème d'isomorphisme des graphes consiste à déterminer si deux graphes sont équivalents malgré des représentations apparemment différentes. Pendant plus de 30 ans, ce problème a résisté aux spécialistes. Bien que les algorithmes pratiques se montrent rapides et trouvent des applications en chimie pour comparer des molécules, il était théoriquement classé comme NP (non polynomial), c'est-à-dire supposément très difficile.

En décembre 2015, Laszlo Babai a révolutionné le domaine en proposant un algorithme fonctionnant en temps quasi-polynomial — bien plus rapide que les temps exponentiels attendus. Cet algorithme décompose les graphes en recherchant leurs symétries selon une procédure récursive. Cependant, Harald Helfgott a identifié une faille en 2017 dans l'étape critique appelée procédure « Split ou Johnson ». Babai a rapidement proposé un correctif que Helfgott a validé lors d'un séminaire Bourbaki.

Ce résultat revêt une importance majeure pour l'informatique théorique, car il ébranle la frontière entre les problèmes réputés faciles (P) et difficiles (NP), touchant directement à la conjecture P = NP, l'un des sept problèmes du millénaire dotés d'un prix d'un million de dollars.