Un chercheur en informatique explore un lien insoupçonné entre l’efficacité des algorithmes et un concept abstrait de la théorie des ensembles, ouvrant potentiellement de nouvelles perspectives sur la complexité computationnelle.
La question de la performance d’un algorithme est centrale en informatique. Les chercheurs s’efforcent de déterminer le nombre d’étapes nécessaires pour résoudre un problème donné. Une observation simple, mais révélatrice, a interpellé Alex Bernshteyn lors d’une récente conférence : un algorithme local capable de résoudre un problème de coloration de graphe avec seulement deux couleurs s’avère extrêmement inefficace. En revanche, l’utilisation de trois couleurs permet de concevoir des algorithmes locaux beaucoup plus performants.
Lors de cette même conférence, un intervenant a évoqué des seuils de performance pour différents types de problèmes. Bernshteyn a alors remarqué une similitude frappante entre l’un de ces seuils et un concept bien connu de la théorie descriptive des ensembles : le nombre de couleurs requis pour colorer certains graphes infinis d’une manière spécifique, dite « mesurable ».
Pour Bernshteyn, cette coïncidence ne pouvait être le fruit du hasard. Il ne s’agit pas simplement de classer les problèmes en fonction de leur efficacité algorithmique, mais de reconnaître que ces problèmes peuvent être formulés en termes de graphes et de colorations. Il a émis l’hypothèse que ces deux domaines, l’informatique et la théorie des ensembles, pourraient être plus étroitement liés qu’il n’y paraît. Il a imaginé une sorte de traduction universelle, où les concepts seraient les mêmes, simplement exprimés dans des langages différents.
Fort de cette intuition, Bernshteyn s’est lancé dans une démarche visant à expliciter ce lien. Son objectif est de démontrer que tout algorithme local efficace peut être transformé en une méthode mesurable au sens de Lebesgue pour colorer un graphe infini, à condition que ce graphe satisfasse certaines propriétés. En d’autres termes, il cherche à établir une équivalence entre une branche essentielle de l’informatique et une branche tout aussi importante de la théorie des ensembles, situées au sommet de la hiérarchie des connaissances.
Son travail s’appuie sur l’étude des problèmes de réseau, un sujet courant dans les cours d’informatique. La règle générale de ces problèmes est que l’algorithme appliqué à un nœud donné ne prend en compte que les informations provenant de son voisinage immédiat, que le graphe comporte mille ou un milliard de nœuds. Pour fonctionner correctement, l’algorithme doit attribuer un numéro unique à chaque nœud d’un quartier donné, permettant ainsi d’enregistrer des informations sur les nœuds proches et de leur donner des instructions. Cette opération est relativement simple à réaliser sur un graphe fini : il suffit d’attribuer un numéro différent à chaque nœud.
Pour aller plus loin
