CHOISIR DES NOMBRES QUI TOMBENT JUSTE, PRESQUE AUSSI VITE QUE LES LIRE

Voici une énigme que tout le monde peut comprendre. Vous avez une liste de nombres entiers — par exemple 3, 9, 14, 20 — et une cible, par exemple 23. Pouvez-vous en choisir certains dont la somme fasse exactement la cible ? (Ici, oui : 3 + 20 ou 9 + 14.) C’est Subset Sum, la « somme de sous-ensemble », l’un des problèmes les plus fondamentaux de l’informatique. L’article le décrit comme un problème NP-complet fondamental, une famille de problèmes connus pour être difficiles à résoudre exactement.

Il existe pourtant une échappatoire. Si les nombres ne sont pas trop grands, des algorithmes astucieux tournent en un temps qui dépend de leur taille. La méthode classique, due à Bellman en 1957, prend un temps proportionnel au nombre d’éléments n multiplié par la cible t. Depuis, les algorithmes n’ont cessé de progresser :

• Pisinger (1999) : proportionnel à n × N, où N est le plus grand nombre ;
• Bringmann (2017) : environ n + t ;
• plusieurs équipes (2021–2024) : environ n + N^(5/3), puis n + N^(3/2).

Le Graal était un temps d’environ n + N — à peine plus que lire les données. Les chercheurs du domaine y voyaient « le problème ouvert le plus crucial » de cette ligne de travaux.

À un cheveu du but

Lin Chen, Yuchen Mao et Guochuan Zhang, de l’université du Zhejiang en Chine, donnent un algorithme qui tourne en temps n + N^(1+ε), où ε peut être n’importe quel petit nombre positif fixé à l’avance — 0,1, 0,01, 0,001. Il est déterministe, accepte nombres négatifs et valeurs répétées, et s’accompagne d’une démonstration mathématique. Les auteurs qualifient ce temps de quasi optimal.

Le résultat s’étend aux vecteurs : choisir des éléments de sorte que plusieurs sommes atteignent leur cible en même temps, en un temps N^(d+ε) pour d coordonnées. Cela répond à son tour à une partie d’une question posée par plusieurs équipes sur la programmation en nombres entiers — trouver des solutions entières à des systèmes d’équations dont les variables sont bornées. Deux conséquences sont détaillées : partager un ensemble de nombres en deux moitiés égales, et répartir des tâches entre deux machines identiques aussi équitablement que possible.

Relever les nombres dans une dimension supérieure

L’idée clé est géométrique. On savait déjà que le problème est facile quand les nombres sont denses et que la cible se trouve bien à l’intérieur de la plage des sommes possibles. L’observation des auteurs : un ensemble de nombres clairsemé peut paraître dense une fois vu dans une dimension supérieure.

Leur exemple est l’ensemble {11, 12, 22, 24}. Écrivez 11 et 22 comme un et deux pas le long d’un premier axe, et 12 et 24 comme un et deux pas le long d’un second. Les sommes possibles remplissent alors chaque point d’un petit carré de 4 sur 4. Mais aplatissez ce carré sur une ligne — en calculant 11x + 12y — et les sommes forment sept amas séparés par des trous, éparpillés entre 0 et 69. Les trous sont une illusion de la projection ; en deux dimensions, la structure est simple.

L’algorithme construit de telles coordonnées en dimension supérieure pour n’importe quelle entrée, à l’aide de résultats de combinatoire additive. À l’intérieur de la région « pleine », les réponses sont immédiates. Seule une zone mince près du bord demande un vrai travail, que l’algorithme découpe en problèmes plus petits résolus récursivement. Chaque étape réduit fortement cette zone, et seul un nombre constant de nouvelles dimensions est jamais ajouté.

Comment la preuve a été construite

L’article s’ouvre sur un « avertissement IA ». Les auteurs ont conçu eux-mêmes la route principale de la preuve, en s’appuyant sur leurs propres travaux récents sur des versions denses et multidimensionnelles du problème. Ils ont ensuite utilisé un modèle d’IA, GPT Astra Ultra, pour transformer ces idées en preuves mathématiques complètes. Il a bloqué sur plusieurs lemmes, débloqués grâce à des idées des auteurs ; une note de recherche publique retrace les conversations. Une fois l’algorithme aléatoire de base obtenu, le modèle l’a étendu aux versions déterministes et multidimensionnelles « sans aucune indication des auteurs ». Le modèle a aussi rédigé l’article et, écrivent les auteurs, vérifié ses principaux résultats par une preuve dans l’assistant Lean 4. Les auteurs assument l’entière responsabilité du contenu.

Pas tout à fait la ligne d’arrivée

L’exposant vaut 1 + ε et non exactement 1, et les constantes cachées grandissent quand ε diminue ; la dépendance au nombre de dimensions n’est pas optimisée. Les auteurs eux-mêmes décrivent l’algorithme comme « assez complexe ». L’article est théorique : il ne rapporte ni implémentation ni mesure de performance.