Un algorithme quasipolynomial pour l'isomorphisme de graphes

La contribution de László Babai fait grand bruit en informatique théorique

La théorie de la complexité, en informatique, classifie les problèmes selon leur difficulté intrinsèque, c’est-à-dire selon la complexité en temps de l’algorithme le plus efficace pour les résoudre. Par exemple, pour trier un tableau, il existe une multitude d’algorithmes  : le tri par insertion, le tri par fusion, le tri par tas ou encore, le plus célèbre, le tri rapide. Les plus efficaces ont une complexité pseudolinéaire : pour trier éléments, il leur faudra opérations ; d’autres algorithmes, comme le tri par insertion, ont une complexité quadratique : le nombre d’opérations évolue comme . Les premiers algorithmes pourront trier des tableaux beaucoup plus grands que les seconds, peu importe le langage de programmation utilisé ou la minutie d’implémentation.

Classes de complexité

En réalité, la théorie de la complexité distingue deux catégories principales de problèmes : ceux qui acceptent une solution en un temps polynomial (des problèmes « faciles »), comme le tri, la recherche de plus court chemin, la multiplication matricielle (ils forment l’ensemble ), puis ceux pour lesquels aucun algorithme polynomial n’est connu, comme le voyageur de commerce ou l’analyse de formules en logique (). Une contrainte supplémentaire pour être dans est qu’il soit possible de vérifier si une réponse est acceptable en un temps polynomial : pour le voyageur de commerce, il suffit de vérifier que toutes les villes sont visitées. Par contre, pour trouver la solution optimale, il n’y a pas de technique qui soit vraiment meilleure que d’explorer toutes les possibilités (du moins, d’un point de vue théorique : il reste possible de résoudre de grandes instances en des temps raisonnables).

En informatique théorique, un problème récurrent est de savoir si . Aucune preuve n’a pu être avancée jusqu’à ce jour, malgré des dizaines d’années d’essais. Si cette égalité était vérifiée, il deviendrait possible de résoudre tous ces problèmes « difficiles » en un temps polynomial — ce qui pourrait changer la face du monde. Rares sont ceux, cependant, qui croient que ces deux classes coïncident : si tel était le cas, on aurait déjà trouvé un algorithme polynomial pour ces problèmes.

Isomorphisme de graphe

Il existe également des problèmes dont on ne sait pas encore s’ils sont dans ou , comme l’isomorphisme de graphes. Il s’agit de déterminer si deux graphes ont la même structure (ils sont alors dits isomorphes), c’est-à-dire si leurs points peuvent correspondre entre eux tout en gardant les liens entre ces points. (Par exemple, les relations d'« amitié » dans un réseau social comme Facebook peuvent être représentées avec des points pour les individus et des liens pour ceux qui se sont déclarés « amis ».)

Les applications de ces isomorphismes sont nombreuses, telle la reconnaissance de l’unicité d’un visiteur sur un site Web de par son comportement ou l’identification de régions pour implanter des infrastructures lors d’une réflexion urbanistique. Un bon nombre de ces applications est cependant de haut vol, comme pour l’optimisation du code dans un compilateur ou, en informatique théorique, la vérification de programmes, notamment dans des contextes parallèles, ou l’égalité de langages reconnus par des automates.

L’avancée de László Babai

Récemment, László Babai a prouvé qu’il existait un algorithme de complexité quasipolynomiale pour résoudre ce problème d’isomorphisme, c’est-à-dire qu’il nécessite un nombre d’opérations (le cas où étant polynomial), par rapport à précédemment. Même si l’avancée semble faible, ce résultat montre que l’isomorphisme a une classe de complexité inférieure à (mais n’est pas forcément dans ).

Toutefois, cet algorithme et les détails de la preuve ne sont pas très accessibles, exploitant la théorie des groupes et les automorphismes de mots. De plus, ce résultat n’aura pas beaucoup d’implications pratiques : ceux qui en ont besoin peuvent résoudre des isomorphismes suffisamment rapidement pour leurs besoins. Certes, ce nouvel algorithme a des garanties théoriques, mais il n’a pas encore fait ses preuves en pratique pour les cas les plus utilisés.


Et alors ?

László Babai a reçu le prix Knuth cette année, décerné par l’ACM, pour ses « contributions fondamentales dans les domaines de la conception d’algorithmes et d’analyse de la complexité ». Le résultat obtenu pour les isomorphismes de graphes est important pour plusieurs raisons, principalement théoriques. Notamment, le lien entre propriétés des groupes et des graphes (les principes sous-jacents pourraient mener rapidement à d’autres résultats du même genre en théorie de la complexité, peut-être même pour donner un algorithme polynomial pour les isomorphismes de graphes). Il faut aussi remarquer que la preuve n’a pas encore été publiée dans une revue avec comité de relecture, mais sur arXiv.

Ce résultat a donc principalement des vertus théoriques. Il pourrait aussi, en pratique, éliminer les parties aléatoires des heuristiques utilisées pour résoudre ces isomorphismes pour n’utiliser que des algorithmes plus classiques dans leur manière de fonctionner ; l’avantage serait alors une bien meilleure prédictibilité des résultats. Il pourrait aussi questionner les pratiques actuelles en cryptographie, en abaissant la classe de complexité du problème de factorisation des nombres entiers.

Voir aussi l’article de László Babai.
Sources : Comparaison de graphes, what are the applications of the isomorphic graphs?, A Big Result On Graph Isomorphism.
Ce contenu a été publié dans Informatique théorique par dourouc05.