UNE BARRIÈRE DE 1962 TOMBE EN INFORMATIQUE

Un cycle hamiltonien est un aller-retour dans un réseau qui passe par chaque point exactement une fois et revient au départ. Dans un réseau orienté, chaque lien est une flèche qu’on ne peut suivre que dans un sens, comme une rue à sens unique. La version pondérée de ce problème est le problème du voyageur de commerce asymétrique.

Décider si un tel cycle existe est un problème difficile de manuel. En 1962, Richard Bellman et, indépendamment, Michael Held et Richard Karp ont donné des algorithmes de programmation dynamique qui le résolvent en un temps d’environ 2ⁿ pour un réseau de n points (à des facteurs près qui ne croissent que de façon polynomiale). Pendant plus de soixante ans, personne n’a fait fondamentalement mieux sur les réseaux orientés en général.

Le cousin non orienté était déjà tombé

Pour les réseaux à liens à double sens, Andreas Björklund a brisé la barrière en 2014 avec un algorithme aléatoire en 1,657ⁿ, travail récompensé par le prix Nerode EATCS-IPEC 2016, selon l’article. C’est toujours le plus rapide connu pour les réseaux non orientés en général. Pour les orientés, les progrès ne concernaient que des cas particuliers — réseaux bipartis, réseaux avec peu de liens par point — ou dépendaient d’une hypothèse non démontrée, la conjecture du rang asymptotique de Strassen.

La nouvelle borne

Tomohiro Koana, de l’université de Tokyo, et Soh Kumabe, de l’entreprise tokyoïte CyberAgent, donnent un algorithme aléatoire qui tranche le problème orienté en un temps

O((375/196)ⁿ) = O(1,9133ⁿ)**.

Pour les réseaux orientés en général, c’est la première amélioration de la base de l’exponentielle depuis 1962.

Compter en pair et impair

La difficulté est subtile. Compter les cycles modulo 2 — savoir seulement si leur nombre est pair ou impair — était déjà possible sous 2ⁿ. Mais un nombre pair non nul de cycles ressemble exactement à zéro. La parade classique consiste à donner aux liens des poids aléatoires pour qu’à un certain poids total, une solution devienne unique (le lemme d’isolement) ; mais la méthode rapide de comptage de parité ne savait pas gérer les poids.

La recette des auteurs, en clair :

1. Deviner une flèche du cycle, et chercher à la place un chemin passant par tous les points d’une extrémité de cette flèche à l’autre.
2. Supprimer chaque flèche au hasard avec une probabilité de 1/50.
3. En chaque point, créer trois groupes de flèches entrantes, et copier chaque flèche restante dans un ensemble non vide de groupes tiré au hasard.
4. Si une tournée existe, alors avec une probabilité d’au moins (49/50)ⁿ⁻¹ on peut choisir un groupe par point de sorte que le nombre de chemins valables soit impair.
5. Donner à chaque groupe — et non à chaque flèche — un poids aléatoire. Le lemme d’isolement fonctionne alors, et environ (50/49)ⁿ répétitions suffisent.
6. Chaque répétition calcule les parités à chaque poids total en un temps (15/8)ⁿ, grâce à des sommes de déterminants de matrices dues à Björklund, Kaski et Koutis et à une « linéarisation » aléatoire utilisée aussi par Arvind et Guruswami.

On multiplie les deux : (50/49)ⁿ × (15/8)ⁿ = (375/196)ⁿ ≈ 1,9133ⁿ.

Une preuve générée par une machine

L’article se termine par une déclaration sur l’IA générative : ChatGPT 6 Astra a généré la preuve du théorème principal et aidé à rédiger le manuscrit. Les auteurs ont fourni les énoncés des propositions intermédiaires, qui donnent une lecture combinatoire de la solution initiale du modèle, puis ont tout vérifié et révisé, et en assument l’entière responsabilité.

Le résultat est théorique — aucun programme n’a tourné — et l’algorithme est aléatoire, avec une petite probabilité d’erreur dans les deux sens. Entre 1,9133 pour les rues à sens unique et 1,657 pour celles à double sens, un large écart reste à combler.