Informatique & IAPreprintThéorie4 min de lecture

TRIER AVEC DES COMPARAISONS INTERDITES, PRESQUE AUSSI VITE

Pour ranger n éléments en les comparant deux à deux, il faut et il suffit d’environ n log n comparaisons — log n, le logarithme, croît très lentement : c’est à peu près le nombre de fois qu’on peut diviser n par deux avant d’arriver à 1. Mais cela suppose que deux éléments quelconques puissent être comparés.

Souvent, ce n’est pas le cas. Les auteurs reprennent un exemple d’un article de 2011 : plusieurs candidats postulent au même emploi, chacun avec des références. Deux candidats ne peuvent être comparés que si une même référence les connaît tous les deux. Les comparaisons permises forment un réseau, un graphe : chaque élément est un point, chaque comparaison autorisée un lien. L’ordre véritable est caché, mais le graphe le contient à coup sûr, sous la forme d’un chemin qui relie chaque élément au suivant. La question : combien de comparaisons faut-il pour retrouver l’ordre ? C’est le tri généralisé.

Pourquoi les astuces habituelles échouent

Les algorithmes classiques supposent une liberté de choix. QuickSort choisit un « pivot » et le compare à la plupart des autres éléments, mais un graphe quelconque peut n’avoir aucun élément relié à la plupart des autres. MergeSort découpe les éléments en groupes qu’il trie séparément, mais un groupe peut ne pas être triable seul : deux éléments voisins dans l’ordre final ne sont pas forcément reliés à l’intérieur du groupe. Plus fondamentalement, le tri ordinaire dispose toujours d’une comparaison qui élimine une bonne part des ordres possibles ; avec des comparaisons restreintes, il peut ne plus y en avoir.

Les progrès ont été lents. En 2011, Zhiyi Huang, Sampath Kannan et Sanjeev Khanna ont trouvé une méthode utilisant environ n¹·⁵ comparaisons, à des facteurs logarithmiques près, et cette borne a tenu depuis pour les graphes quelconques. Ces auteurs se demandaient même si le problème n’était pas fondamentalement plus dur que le tri ordinaire, au point d’exiger n élevé à une puissance supérieure à 1.

Prédire d’abord, réparer ensuite

Sanjeev Khanna, de l’université de New York, Aaron Putterman, de l’université Harvard, et Junkai Song, également de l’université de New York, répondent aujourd’hui à cette question : non. Leur algorithme aléatoire, qui fait des choix au hasard en cours de route, trie avec environ n log⁴ n comparaisons en moyenne, sur n’importe quel graphe — à peine quelques facteurs logarithmiques au-dessus du tri ordinaire. Et il est, selon les auteurs, « relativement simple ». Le gain reste théorique : les constantes de la preuve sont énormes (des facteurs comme 2³²), si bien que l’avantage n’apparaît que pour des n très grands.

Il s’appuie sur un résultat connu : si l’on vous donne, pour chaque lien, une supposition sur celui de ses deux éléments qui vient en premier, fausse pour w d’entre eux, l’ordre se retrouve en environ n log n + w comparaisons. La tâche devient donc de produire une supposition avec peu d’erreurs, en peu de comparaisons. Les étapes clés :

  • Une première ébauche grossière. Comparer un échantillon aléatoire de paires reliées et prendre n’importe quel ordre compatible avec les réponses. Elle fait beaucoup d’erreurs, mais pas trop.
  • Isoler les erreurs plutôt que les corriger. Au lieu de rectifier les suppositions fausses, l’algorithme repère les zones du graphe où les erreurs sont plus denses que la moyenne et les met de côté. Chaque tour divise en moyenne par quatre le nombre d’erreurs restantes.
  • Y revenir plus tard. Les liens mis de côté sont traités lors d’une phase suivante. Chaque phase règle au moins la moitié des liens encore en attente : le nombre de phases ne croît que comme le logarithme du nombre de liens : un million de liens, environ 2²⁰, en demandent une vingtaine.

Une preuve trouvée avec des machines

La déclaration d’usage de l’IA est d’une précision inhabituelle. Elle affirme que ChatGPT 6-Astra « a été essentiel pour prouver les bornes améliorées ». Un modèle a d’abord trouvé un algorithme utilisant environ n¹·³³ comparaisons, puis a calé. Les auteurs sont descendus à n¹·² ; ensuite, sollicités des dizaines de fois pendant plusieurs semaines, des modèles ont trouvé des améliorations successives — n^(10/9), n^(17/16), n^(19/18) — avant d’atteindre l’algorithme quasi linéaire. Les auteurs ajoutent qu’on ne sait pas si leur propre étape intermédiaire a été indispensable à cette découverte finale.

Ce qui reste ouvert

Le résultat compte des comparaisons, pas un temps de calcul : en l’état, l’algorithme ne s’exécute pas en temps polynomial : il fait peu de comparaisons, mais son temps de calcul explose quand n grandit, car à une étape il essaie tous les ordres possibles d’un ensemble d’éléments. La méthode de 2011 n’avait pas ce défaut. Les auteurs listent trois questions ouvertes : peut-on supprimer les facteurs logarithmiques restants, un algorithme sans hasard peut-il faire aussi bien, et un algorithme efficace peut-il atteindre le même nombre de comparaisons — ou même simplement battre n¹·⁵ ?