💻 informatique

Truly Subquadratic 3SUM and Truly Subcubic APSP via Triangles in Sparse Lopsided Graphs

Ce document présente les premières améliorations polynomiales des algorithmes classiques pour 3SUM et All-Pairs Shortest Paths (APSP) en introduisant un nouvel algorithme pour calculer les entrées creuses de produits de matrices dans des graphes asymétriques, ce qui réfute les hypothèses 3SUM et APSP et produit des accélérations pour de nombreux problèmes connexes.

Auteurs originaux : Josh Alman, Virginia Vassilevska Williams

Publié 2026-10-06

📖 5 min de lecture🧠 Analyse approfondie

CC BY 4.0

Auteurs originaux : Josh Alman, Virginia Vassilevska Williams

Article original sous licence CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ Ceci est une explication générée par l'IA de l'article ci-dessous. Elle n'a pas été rédigée ni approuvée par les auteurs. Pour une précision technique, consultez l'article original. Lire la clause de non-responsabilité complète

Dans le vaste paysage de l'informatique, il existe des problèmes qui ont résisté obstinément à toute amélioration pendant des décennies, agissant comme des ralentisseurs sur notre capacité à traiter l'information plus rapidement. Deux des plus célèbres sont le problème du « trois-somme » (three-sum) et le problème des « plus courts chemins entre toutes les paires » (all-pairs shortest paths). Le premier pose une question simple : étant donné une liste de nombres, pouvez-vous en trouver trois dont la somme est égale à zéro ? Pendant longtemps, la meilleure façon de résoudre cela pour une grande liste de nombres demandait un temps qui augmentait avec le carré de la taille de la liste. Le second problème demande la distance la plus courte entre chaque paire de villes dans un réseau routier. La meilleure méthode connue pour cela a toujours pris un temps qui croît avec le cube du nombre de villes. Pendant des années, les informaticiens ont cru que ces limites étaient incassables, formant un ensemble de règles appelées « hypothèses » qui suggéraient qu'aucun algorithme ne pourrait jamais être significativement plus rapide que ces méthodes classiques. Ces problèmes ne sont pas seulement des puzzles abstraits ; ils sous-tendent tout, de la cartographie logicielle à la détection de motifs dans des données complexes, de sorte que trouver un moyen de briser ces limites de vitesse constituerait un changement monumental dans notre façon de calculer.

Une équipe de chercheurs de l'Université Columbia et du MIT, travaillant avec un modèle d'intelligence artificielle développé par Anthropic, a maintenant brisé ces croyances de longue date. Ils ont découvert une nouvelle façon de résoudre ces problèmes qui est véritablement plus rapide que les meilleures méthodes précédentes. Au lieu de prendre un temps proportionnel au carré de la taille de l'entrée pour le problème du trois-somme, leur nouvelle méthode le résout en un temps légèrement inférieur au carré. De même, pour le problème des plus courts chemins, ils ont réduit le temps requis à légèrement moins du cube du nombre de villes. Il ne s'agit pas d'une modification mineure ou d'une astuce qui ne fonctionne que dans des cas particuliers ; c'est une amélioration fondamentale qui s'applique à un large éventail d'entrées. En prouvant que ces problèmes peuvent être résolus plus rapidement, les chercheurs ont effectivement réfuté les hypothèses qui affirmaient qu'ils ne le pouvaient pas.

Le secret de cette percée réside dans une nouvelle approche ingénieuse de la multiplication de matrices, qui sont simplement des grilles de nombres utilisées pour représenter des données. Les chercheurs se sont concentrés sur un type spécifique de multiplication de matrices où les grilles sont très fines et longues, plutôt que carrées. Ils ont réalisé que si vous n'avez besoin de connaître les réponses que pour quelques endroits spécifiques dans le résultat final, plutôt que de calculer chaque nombre de la grille entière, vous pouvez économiser une quantité massive de travail. Ils ont conçu un algorithme qui agit comme un filtre hautement efficace, ignorant les calculs qui produiraient des réponses dont personne n'a besoin. Cette technique a été construite en modifiant une identité mathématique plus ancienne, un ensemble de règles pour combiner des nombres, pour qu'elle ne travaille que sur les parties spécifiques d'informations qui importaient.

La puissance de cette découverte vient de la manière dont ces différents problèmes informatiques sont connectés. Dans le monde de la complexité fine, les chercheurs ont passé des années à cartographier la façon dont la résolution d'un problème aide à en résoudre un autre. Ils ont découvert que si vous pouvez résoudre le problème du « trois-somme » plus rapidement, vous pouvez également résoudre le problème des « plus courts chemins » plus rapidement, et vice versa. Le nouvel algorithme agit comme une clé maîtresse. En déchiffrant le code pour ce problème spécifique de multiplication de matrices, les chercheurs ont débloqué des solutions plus rapides pour des dizaines d'autres problèmes qui étaient auparavant considérés comme bloqués à leurs anciennes vitesses. Cela inclut la recherche de triangles dans des réseaux, la vérification de motifs spécifiques dans des données, et l'optimisation de divers types de tâches de recherche et de tri.

L'équipe n'a pas seulement trouvé une possibilité théorique ; elle a fourni une méthode concrète et déterministe qui fonctionne à chaque fois. Ils ont également montré que leur approche fonctionne même lorsque les nombres impliqués ne sont pas seulement des nombres entiers mais des nombres réels, qui sont les types de valeurs utilisés dans la plupart des calculs scientifiques du monde réel. Les chercheurs ont utilisé un outil d'IA puissant pour aider à vérifier leurs preuves mathématiques, garantissant que la logique derrière leur accélération était solide. Cette collaboration entre chercheurs humains et intelligence artificielle met en lumière une nouvelle ère de découverte scientifique, où les machines peuvent aider à découvrir des vérités mathématiques profondes qui pourraient échapper aux humains.

Les implications de ce travail s'étendent bien au-delà des problèmes spécifiques du trois-somme et des plus courts chemins. Cela remet en question l'idée que certaines limites de calcul sont absolues. Pendant des décennies, la communauté a accepté que certains problèmes nécessitent un temps spécifique pour être résolus, et que tenter d'aller plus vite était futile. Cette publication démontre que ces limites n'étaient pas des murs, mais simplement des plafonds qui pouvaient être élevés avec la bonne perspective. Bien que les nouveaux algorithmes soient actuellement trop complexes pour être utilisés dans les logiciels de tous les jours en raison des énormes constantes cachées dans leur vitesse, la preuve de leur existence change le fondement théorique de l'informatique. Cela ouvre la porte à de futurs chercheurs pour affiner ces méthodes, menant potentiellement à des outils pratiques capables de traiter des ensembles de données massifs beaucoup plus efficacement qu'auparavant. Les chercheurs ont montré que même les problèmes les plus tenaces peuvent céder à une pensée fraîche, prouvant que les frontières de ce qui est calculable méritent toujours d'être testées.

Résumé Technique : 3SUM véritablement sous-quadratique et APSP véritablement sous-cubique via des triangles dans des graphes creux lopsides

1. Énoncé du Problème

Cet article traite de deux problèmes fondamentaux de la théorie de la complexité à granularité fine qui résistent à toute amélioration significative depuis des décennies :

3SUM : Étant donné $n$ entiers de taille polynomiale, déterminer si trois d'entre eux somment à zéro. L'algorithme standard s'exécute en un temps de $O(n^2)$ , et l'Hypothèse 3SUM postule qu'aucun algorithme ne peut résoudre ce problème en $O(n^{2-\epsilon})$ pour tout $\epsilon > 0$ .
All-Pairs Shortest Paths (APSP - Chemins les plus courts entre toutes les paires) : Étant donné un graphe orienté avec $n$ sommets et des poids entiers à croissance polynomiale, calculer le chemin le plus court entre toutes les paires de sommets. Les algorithmes standards (Floyd-Warshall, Johnson) s'exécutent en $O(n^3)$ temps. L'Hypothèse APSP postule qu'aucun algorithme ne peut résoudre ce problème en $O(n^{3-\epsilon})$ temps.

L'article cible également le problème du Triangle Exact (trouver un triangle dont la somme totale des poids des arêtes est nulle dans un graphe tripartite) ainsi que le problème de l'APSP non pondéré orienté et une grande variété de problèmes équivalents à ceux-ci par des réductions à granularité fine (par exemple, le produit $(\min, +)$ , la distance d'édition d'arbre, le $k$ -clique de poids nul).

2. Méthodologie

La contribution centrale est un nouvel algorithme pour calculer un ensemble prescrit d'entrées dans le produit de deux matrices « minces » (thin).

2.1 Algorithme de Produit de Matrices Minces

Les auteurs développent un algorithme déterministe pour calculer un ensemble $W$ d'entrées dans le produit $XY$ , où :

$X$ est une matrice entière de taille $N \times D$ .
$Y$ est une matrice entière de taille $D \times N$ .
$D \le N^{1/18}$ (les matrices sont « minces »).
$W$ est un ensemble d'au plus $N^2/\sqrt{D}$ positions.

Innovation Technique Clé :
L'algorithme modifie l'algorithme de multiplication de matrices rectangulaires de Coppersmith, qui repose lui-même sur une identité à dix multiplications de Schönhage.

Structure Récursive : L'algorithme applique l'identité de Schönhage de manière récursive. Contrairement à la multiplication de matrices standard qui calcule toutes les $N^2$ entrées, cet algorithme élague l'arbre de récursion.
Stratégie d'Élagage : Il ne visite que les « feuilles » de l'arbre de récursion nécessaires pour calculer les entrées de $W$ .
Partage d'Encodage : La phase d'« encodage » (combinaisons linéaires des blocs d'entrée) dépend uniquement des matrices d'entrée, et non des entrées de sortie spécifiques. L'algorithme calcule ces encodages une seule fois par bloc d'entrée et les partage pour tous les calculs requis.
Analyse des Feuilles : Les auteurs analysent l'« ordre » des feuilles dans l'arbre de récursion. Ils prouvent que, bien qu'une seule entrée de sortie nécessite de nombreuses feuilles, la plupart des feuilles sont partagées entre de nombreuses entrées de sortie. En équilibrant soigneusement le nombre de feuilles de différents ordres, ils démontent que le nombre total de feuilles requises pour un ensemble $W$ creux est nettement inférieur au coût du calcul du produit complet ou du calcul individuel des entrées.

Complexité :
L'algorithme calcule les entrées de $W$ en $O(N^2 / D^{0.063})$ temps (avec des facteurs logarithmiques), ce qui est polynomialement plus rapide que le temps $O(N^2)$ requis pour écrire le produit complet ou le temps $O(N^2 \sqrt{D})$ requis pour calculer les entrées individuellement comme des produits scalaires.

2.2 Réductions vers les Problèmes de Graphes

L'algorithme de matrice est appliqué au problème du Lopsided All-Edges Sparse Triangle (Triangle Creux de Toutes les Arêtes Lopsided). Dans ce problème, on cherche à déterminer si un ensemble d'arêtes $(a, b)$ dans un graphe tripartite (avec des parties $A, B$ de taille $n$ et une partie intermédiaire $M$ de taille $D \ll n$ ) appartient à un triangle.

Interprétation Matricielle : Cela équivaut à calculer les entrées du produit des matrices de bi-adjacence du graphe aux positions correspondant aux arêtes de $W$ .
Réduction Déterministe : L'article fournit une réduction déterministe du Triangle Exact (sur des graphes généraux) vers le Lopsided All-Edges Sparse Triangle. Cela implique de hacher les poids des arêtes modulo un nombre premier choisi de manière déterministe pour minimiser les faux positifs, suivi d'une recherche de témoin.
Chaîne de Réductions : Des réductions à granularité fine connues lient 3SUM et APSP au Triangle Exact. En composant ces réductions avec le nouvel algorithme pour le Lopsided All-Edges Sparse Triangle, les auteurs dérivent des algorithmes plus rapides pour les problèmes originaux.

3. Contributions Clés et Résultats

3.1 Réfutation des Hypothèses

L'article présente les premières améliorations polynomiales par rapport aux algorithmes classiques pour 3SUM et APSP, réfutant ainsi les hypothèses de complexité à granularité fine pour 3SUM et APSP.

3SUM : Résolu de manière déterministe en $O(n^{1.9992})$ temps pour des entiers de taille polynomiale.
APSP : Résolu de manière déterministe en $O(n^{2.9995})$ temps pour des graphes orientés avec des poids entiers à croissance polynomiale.
Exact Triangle : Résolu de manière déterministe en $O(n^{2.9983})$ temps.
Directed Unweighted APSP : Résolu de manière déterministe en $O(n^{2+\mu-\epsilon})$ temps (où $\mu < 0.5275$ ), réfutant l'hypothèse selon laquelle l'algorithme de Zwick est optimal. C'est la première amélioration qui ne découle pas uniquement de l'accélération des bornes de multiplication de matrices rectangulaires.

3.2 Variantes à Valeurs Réelles

En utilisant une réduction de Chan, Vassilevska Williams et Xu qui repose uniquement sur les comparaisons, les additions et les soustractions, les auteurs fournissent des algorithmes Las Vegas (randomisés avec erreur nulle) pour les versions à valeurs réelles de ces problèmes :

Real 3SUM : Temps espéré de $O(n^{1.998})$ .
Real APSP : Temps espéré de $O(n^{2.998})$ .

3.3 Impact Algorithmique Global

À travers des réductions connues, la nouvelle technique permet des accélérations polynomiales pour un large éventail d'autres problèmes, notamment :

Le produit $(\min, +)$ de matrices.
La Distance d'Édition d'Arbre (pour des coûts entiers à croissance polynomiale).
Le Zero-Weight, Min-Weight, et Max-Weight $k$ -Clique pour tout $k \ge 3$ constant.
Conjectures Online Matrix-Vector (OMv) : L'article réfute les variantes « suggérées » de la conjecture OMv (spécifiquement pour les indices fins) en fournissant une structure de données qui pré-traite les matrices en sous-temps quadratique et répond aux requêtes d'entrée unique en sous-temps linéaire par rapport à la dimension interne.
Knapsack (Sac à dos) et Approximate Subset Sum : Premiers algorithmes véritablement sous-quadratiques pour l'Unbounded Knapsack et des schémas d'approximation pour le Subset Sum.

3.4 Version Structure de Données

Les auteurs étendent l'algorithme de matrice en une structure de données. Après un pré-traitement de $X$ et $Y$ en $O(N^2/D^{0.063})$ temps, n'importe quelle entrée $(XY)[I, J]$ peut être calculée en $O(D^{0.437})$ temps. Cela permet de résoudre des problèmes où les entrées cibles ne sont pas connues à l'avance.

4. Signification et Revendications

Les auteurs considèrent ce travail comme un « grand succès pour la complexité à granularité fine ».

Réductions comme Algorithmes : L'article souligne que les réductions à granularité fine, précédemment utilisées principalement pour inférer une dureté conditionnelle, sont aussi des algorithmes. Une seule nouvelle technique (l'algorithme de produit de matrices minces) peut accélérer simultanément un vaste réseau de problèmes interconnectés.
Réfutation du Statu Quo : Les résultats démontrent que les temps d'exécution « bloqués » pour 3SUM et APSP n'étaient pas des barrières fondamentales mais plutôt des artefacts des techniques disponibles à l'époque.
Limites et Questions Ouvertes :
- Les auteurs notent que leurs techniques n'améliorent pas actuellement CNF-SAT, Orthogonal Vectors, ou $k$ -SUM pour $k \ge 4$ , car ces problèmes ne se réduisent pas aux instances spécifiques de triangles creux résolues ici.
- Les algorithmes sont algébriques et possèdent actuellement de grandes constantes cachées, ce qui les rend peu pratiques pour une utilisation immédiate dans le monde réel.
- Le cas équilibré (balanced) de l'All-Edges Sparse Triangle (où les trois parties sont toutes de taille $n$ ) reste non résolu par cette technique, laissant intacte l'hypothèse $m^{4/3}$ pour ce cas spécifique.
- L'article ne prétend pas avoir trouvé l'exposant optimal pour ces problèmes, notant que d'autres améliorations sont probablement possibles grâce à de meilleures réductions ou des identités algébriques affinées.

5. Note Méthodologique sur la Découverte

L'article reconnaît explicitement que l'algorithme central a été découvert par Claude, un modèle d'IA développé par Anthropic. Les auteurs (Josh Alman et Virginia Vassilevska Williams) ont travaillé pour comprendre, simplifier, renforcer et étendre l'algorithme, en dériver les conséquences et en formaliser les résultats. Les principaux résultats ont été vérifiés à l'aide de l'assistant de preuve Lean 4. Les auteurs assument l'entière responsabilité du contenu et de la présentation de l'article.