Informatique & IAPreprintThéorie4 min de lecture

LA LIMITE DE VITESSE POUR TROUVER DES CLIQUES TOMBE APRÈS 40 ANS

Imaginez un réseau social de n personnes. Existe-t-il un groupe de k d’entre elles qui se connaissent toutes ? Les informaticiens appellent un tel groupe une k-clique, et la trouver est un problème classique aux applications innombrables. L’approche naïve vérifie chaque groupe possible de k personnes, environ n^k groupes — sans espoir pour de grands réseaux.

Une astuce de 1985 et un long défi

Il y a plus de 40 ans, Jaroslav Nešetřil et Svatopluk Poljak ont trouvé un raccourci : ramener la recherche d’une k-clique à celle d’un triangle (trois points tous reliés entre eux) dans un réseau plus grand — un « graphe », dans le jargon du domaine —, qu’on peut à son tour faire en multipliant des matrices, de grands tableaux de nombres. Le coût dépend de ω, l’exposant de la multiplication de matrices : multiplier deux tableaux de n sur n nombres demande environ n^ω étapes. Leur méthode demande environ n^(ωk/3) étapes. Personne ne connaît ω exactement. Il vaut au moins 2, et au plus 9/4 (2,25), d’après une prépublication récente citée par l’article.

L’exposant de cette méthode de 1985 n’a jamais été battu. En 2004, Gerhard Woeginger a mis les chercheurs au défi de faire mieux pour un k fixé ; plus de deux décennies ont passé. Entre-temps, l’hypothèse k-Clique — n^(ωk/3) serait en substance le mieux possible — est devenue une fondation de la « complexité fine », le domaine qui cherche le coût exact des problèmes de calcul. Les chercheurs s’en servaient pour soutenir que bien d’autres problèmes, de l’analyse de grammaires à l’étude de données compressées, ne pouvaient pas non plus être résolus plus vite.

Une cible mouvante

Réfuter cette hypothèse posait une difficulté particulière. Son coût prédit dépend de ω, qui est inconnu. Un algorithme qui bat la meilleure valeur actuelle de ω pourrait cesser de battre l’hypothèse si quelqu’un trouvait plus tard une multiplication de matrices plus rapide.

Virginia Vassilevska Williams, du MIT, et Or Zamir, de l’université de Tel-Aviv, contournent le problème. Leur preuve : pour tout k assez grand, on peut trouver — et même compter — les k-cliques en environ n^((ω/3 − c)k) étapes, où c est une constante positive qui ne dépend ni de k ni de ω. Le gain se mesure par rapport à la vraie valeur de ω, quelle qu’elle soit. Il tient même si ω = 2, le meilleur cas imaginable.

Plier un coin

En bref : les auteurs découpent un gros calcul en quelques cas plus simples plus un reste bon marché, qui coûtent ensemble un peu moins que le tout. Le cœur de la méthode porte sur des motifs de neuf sommets (les points du réseau) reliés par des arêtes (les liens entre eux). L’approche standard les répartit en trois groupes de trois et multiplie trois énormes matrices. Les auteurs regardent un coin — deux arêtes qui partagent un sommet — et insèrent, entre deux des matrices, un tableau qui ne change rien : l’identité. Cette identité est ensuite écrite comme la somme de quelques « échanges », dont chacun fusionne les deux arêtes du coin en une seule, plus un reste de faible rang — un tableau qui, malgré sa taille, contient peu d’information indépendante et coûte donc peu à multiplier.

Les échanges donnent des motifs plus simples, avec moins d’arêtes, traités à leur tour par la même méthode ; un motif à neuf sommets a au plus 36 arêtes, donc la récursion s’arrête. Le reste de faible rang rétrécit les matrices à multiplier. Appliquer l’astuce à deux coins séparés à la fois est ce qui garde un gain même quand ω = 2. Tout k multiple de neuf peut ensuite être regroupé en neuf blocs.

Réel mais infime

Les auteurs ne chiffrent pas le gain. Selon l’article, les constantes iraient « de minuscules sans optimisation à infimes avec des optimisations importantes ». L’enjeu n’est pas la vitesse en pratique : c’est qu’une barrière à laquelle on croyait depuis des décennies n’existe pas.

Les conséquences dépassent les cliques. Les algorithmes exacts de problèmes d’optimisation difficiles comme Max-Cut et Max-2-SAT, qui demandaient environ 2^(ωn/3) étapes pour n variables, obtiennent eux aussi un exposant plus petit. Tout comme le comptage des copies d’un petit graphe fixé.

Ce qu’a fait l’IA

Dans une section dédiée, les auteurs racontent leur travail avec ChatGPT-6, utilisé par son interface web publique. Partant de leurs propres idées pour les cliques de cinq personnes et d’un récent résultat d’OpenAI qui réfute une autre conjecture, l’hypothèse du temps exponentiel, le modèle a trouvé une première amélioration, compliquée, pour les 5-cliques. Les auteurs l’ont ensuite distillée, avec l’aide de l’IA, en la décomposition algébrique au cœur de la preuve, considérée dans l’article comme « presque purement la contribution de l’IA ». Le cadre algorithmique construit autour vient, selon l’article, surtout de l’équipe.

Une remarque se détache. Les preuves obscures générées par l’IA sont difficiles à lire pour les humains, notent les auteurs — et, ce qui les a frappés, difficiles à comprendre aussi pour l’IA elle-même.