Un problème qui semble facile donne des chiffres trop grands pour notre univers | Magazine Quanta

Ce n’est pas souvent que des enfants de 5 ans peuvent comprendre des questions aux frontières de l’informatique, mais cela peut arriver. Supposons, par exemple, qu’une enfant de maternelle nommée Alice ait deux pommes, mais qu’elle préfère les oranges. Heureusement, ses camarades de classe ont développé un système d'échange de fruits sain avec des taux de change strictement appliqués : abandonnez une pomme, par exemple, et vous pouvez obtenir une banane. Alice peut-elle exécuter une série de transactions, en ramassant et en déchargeant des bananes ou des cantaloups, qui l'amènent à son fruit préféré ?

Cela semble assez simple. « Vous pouvez aller à l’école primaire et le dire aux enfants », a déclaré Christophe Haase, informaticien à l'Université d'Oxford. « Les gens penseront : « Cela doit être facile. »

Mais le problème mathématique qui sous-tend le dilemme d'Alice – appelé problème d'accessibilité pour les systèmes d'addition de vecteurs – est étonnamment subtil. Même si certains cas peuvent être résolus facilement, les informaticiens ont lutté pendant près d’un demi-siècle pour parvenir à une compréhension globale du problème. Aujourd’hui, grâce à une série de progrès réalisés au cours des dernières années, ils ont clairement établi à quel point ce problème peut devenir complexe.

Il s’avère que ce problème enfantin est d’une complexité absurde, presque caricaturale – si complexe que pratiquement tous les autres problèmes de calcul célèbres et difficiles ça ressemble à un jeu d'enfant. Essayez de quantifier l'effort requis pour résoudre ce problème, et bientôt vous serez confronté à des nombres si grands que même en comptant leurs chiffres, vous atteindrez des nombres dont vous n'avez jamais entendu parler. De tels chiffres invitent souvent à des comparaisons à l’échelle de l’univers, mais même ces analogies ne suffisent pas. "Cela ne lui rendrait pas justice", a déclaré Georg Zetzsche, informaticien à l'Institut Max Planck pour les systèmes logiciels de Kaiserslautern, en Allemagne. "L'univers est si petit."

À portée de main?

Réduit à son essence, le problème d’accessibilité concerne des objets mathématiques appelés vecteurs, qui sont des listes ordonnées de nombres. Les entrées de ces listes sont appelées composants, et le nombre de composants dans un vecteur est appelé sa dimensionnalité. L'inventaire des fruits d'Alice, par exemple, peut être décrit par un vecteur à quatre dimensions (a, b, c, d), dont les composants représentent le nombre de pommes, bananes, cantaloups et oranges dont elle dispose à un moment donné.

Un système d'addition de vecteurs, ou VAS, est un ensemble de vecteurs représentant les transitions possibles entre les états d'un système. Pour Alice, le vecteur de transition (−1, −1, 1, 0) représenterait l'échange d'une pomme et d'une banane contre un cantaloup. Le problème d'accessibilité du VAS demande s'il existe une combinaison de transitions autorisées qui peut vous faire passer d'un état initial spécifique à un état cible spécifique - ou, en termes mathématiques, s'il existe une somme de vecteurs de transition qui transforme le vecteur de départ en vecteur cible. Il n’y a qu’un seul problème : aucune composante du vecteur décrivant l’état du système ne peut jamais descendre en dessous de zéro.

"C'est une restriction très naturelle pour un modèle de réalité", a déclaré Wojciech Czerwinski, informaticien à l'Université de Varsovie. "Vous ne pouvez pas avoir un nombre négatif de pommes."

Dans certains systèmes, il est facile de déterminer si le vecteur cible est atteignable. Mais ce n'est pas toujours le cas. Les informaticiens sont plus intéressés par les systèmes d'addition de vecteurs d'apparence simple dans lesquels il n'est pas évident de déterminer à quel point il est difficile de déterminer l'accessibilité. Pour étudier ces cas, les chercheurs commencent par définir un nombre qui quantifie la taille d’un système donné. Ce numéro, représenté par n, englobe le nombre de dimensions, le nombre de transitions et d’autres facteurs. Ils se demandent ensuite à quelle vitesse la difficulté du problème d’accessibilité peut augmenter à mesure que n grandit.

Pour répondre à cette question, les chercheurs utilisent deux approches complémentaires. Premièrement, ils recherchent des exemples de systèmes d’addition de vecteurs particulièrement délicats dans lesquels la détermination de l’accessibilité nécessite un minimum d’effort. Ces niveaux minimaux sont appelés « limites inférieures » de la complexité du problème – disent-ils aux chercheurs : « Les systèmes les plus délicats pour un problème donné n sont au moins aussi difficiles.

Deuxièmement, les chercheurs tentent d’établir des « limites supérieures » – des limites à la difficulté d’accès, même dans les systèmes les plus diaboliques. Ceux-ci disent : « Les cas les plus délicats pour un n sont tout au plus aussi difficiles. Pour déterminer précisément à quel point l'accessibilité est difficile dans les systèmes les plus délicats, les chercheurs tentent de pousser les limites inférieures vers le haut et les limites supérieures vers le bas jusqu'à ce qu'elles se rencontrent.

Les trucs des cauchemars

Les systèmes d’addition de vecteurs ont une longue histoire. Depuis les années 1960, les informaticiens les utilisent pour modéliser des programmes qui divisent un calcul en plusieurs petits éléments et travaillent simultanément sur ces éléments. Ce type de « calcul simultané » est désormais omniprésent, mais les chercheurs n'en comprennent pas encore pleinement les fondements mathématiques.

En 1976, l'informaticien Richard Lipton a fait le premier pas vers la compréhension de la complexité du problème d’accessibilité du VAS. Il a développé une procédure de construction de systèmes dans laquelle le moyen le plus rapide de déterminer si un état est accessible depuis un autre est de tracer une séquence de transitions entre eux. Cela lui a permis d’utiliser la longueur du chemin le plus court entre deux États soigneusement choisis comme mesure de la difficulté du problème d’accessibilité.

Lipton alors prouvé il pourrait construire un système de taille n dans lequel le chemin le plus court entre deux états impliquait plus de transitions $latex 2^{2^n}$. Cela impliquait une double limite inférieure exponentielle correspondante sur l’effort requis pour déterminer l’accessibilité dans ses systèmes. Ce fut une découverte surprenante : la croissance double exponentielle fait partie des cauchemars des informaticiens. En effet, les chercheurs rechignent souvent même à une croissance exponentielle ordinaire, qui n'est rien en comparaison : $latex {2^5}= 32$, mais $latex 2^{2^5}$ dépasse 4 milliards.

La plupart des chercheurs pensaient que Lipton avait concocté les systèmes d'addition de vecteurs les plus complexes possibles, ce qui signifie qu'il avait élevé la limite inférieure aussi haut que possible. La seule chose qui manquerait, dans ce cas, serait une limite supérieure qui l’accompagnerait, c’est-à-dire une preuve qu’il ne pourrait y avoir de système dans lequel déterminer l’accessibilité serait encore plus difficile. Mais personne ne savait comment le prouver. L'informaticien Ernst Mayr s'en est rapproché lorsqu'il prouvé en 1981, il est toujours possible, en principe, de déterminer l'accessibilité dans n'importe quel système d'addition de vecteurs. Mais sa preuve n’a fixé aucune limite quantitative à la gravité du problème. Il y avait un sol, mais aucun plafond en vue.

"J'y ai certainement pensé de temps en temps", a déclaré Lipton. "Mais au bout d'un moment, j'ai abandonné et, d'après ce que j'ai pu constater, personne n'a fait de progrès pendant environ 40 ans."

En 2015, les informaticiens Jérôme Leroux ainsi que le Sylvain Schmitz finalement établi une borne supérieure quantitative – un niveau si élevé que les chercheurs ont supposé qu'il ne s'agissait que d'un premier pas qui pourrait être abaissé pour atteindre la limite inférieure de Lipton.

Mais ce n'est pas ce qui s'est passé. En 2019, des chercheurs ont découvert une limite inférieure bien supérieure à celle de Lipton, bouleversant des décennies de sagesse conventionnelle. Le problème d’accessibilité du VAS était bien plus complexe que prévu.

Une tour de pouvoirs

Le résultat choquant de 2019 est le résultat d’un échec. En 2018, Czerwiński a réfuté une conjecture de Leroux et Filip Mazowiecki, informaticien aujourd'hui à l'Université de Varsovie, cela aurait permis de progresser sur un problème connexe. Au cours de discussions ultérieures, les chercheurs ont découvert une nouvelle façon prometteuse de construire des systèmes d'addition de vecteurs extra-complexes, ce qui pourrait impliquer une nouvelle limite inférieure pour le problème d'accessibilité du VAS, où les progrès étaient au point mort depuis si longtemps.

"Dans mon esprit, tout était lié à l'accessibilité du VAS", se souvient Czerwiński. Au cours d'un semestre à faible charge d'enseignement, il décide de se concentrer exclusivement sur cette problématique, avec Leroux, Mazowiecki et deux autres chercheurs : Slawomir Lasota de l'Université de Varsovie et Ranko Lazić de l'Université de Warwick.

Au bout de quelques mois, leurs efforts ont payé. Czerwiński et ses collègues démontré qu'ils pouvaient construire des systèmes d'addition de vecteurs dans lesquels le chemin le plus court entre deux états était lié à la taille du système par une opération mathématique appelée tétration qui rend même une double croissance exponentielle cauchemardesque apprivoisée.

La tétration est une extension simple d'un modèle reliant les opérations les plus familières en mathématiques, en commençant par l'addition. Additionner n copies d'un nombre, et le résultat équivaut à multiplier ce nombre par n. Si vous multipliez ensemble n copies d'un nombre, cela équivaut à une exponentiation, ou à élever le nombre au nla puissance. La tétration, souvent représentée par une paire de flèches pointant vers le haut, est l'étape suivante de cette séquence : tétrater un nombre par n signifie l'exponentier n fois pour produire une tour de pouvoirs n étages.

Il est difficile de comprendre à quelle vitesse la tétration devient incontrôlable : $latex 2 uparrowuparrow 3$, ou $latex 2^{2^2}$, vaut 16, $latex 2 uparrowuparrow 4$ vaut un peu plus de 65,000 2, et $latex 5 uparrowuparrow 20,000$ est un nombre de près de 2 6 chiffres. Il est physiquement impossible d'écrire tous les chiffres de $latex XNUMX uparrowuparrow XNUMX$ – une responsabilité de vivre dans un si petit univers.

Dans leur résultat marquant, Czerwiński et ses collègues ont prouvé qu'il existe des systèmes d'addition vectorielle de taille n où la meilleure façon de déterminer l'accessibilité est de tracer un chemin impliquant plus de $latex 2 uparrowuparrow n$ transitions, impliquant une nouvelle limite inférieure qui éclipse celle de Lipton. Mais aussi vertigineuse que soit la tétration, elle ne constitue pas encore le dernier mot sur la complexité du problème.

Vers Quinquagintillion et au-delà 

Quelques mois seulement après la nouvelle limite inférieure choquante sur la complexité de l'accessibilité du VAS, Leroux et Schmitz rabaisser la limite supérieure qu'ils avaient établie trois ans plus tôt, mais ils ne sont pas parvenus jusqu'à la tétration. Au lieu de cela, ils ont prouvé que la complexité du problème d’accessibilité ne peut pas croître plus rapidement qu’une monstruosité mathématique appelée fonction d’Ackermann.

Pour comprendre cette fonction, prenons le modèle utilisé pour définir la tétration jusqu’à sa sombre conclusion. L'opération suivante dans la séquence, appelée pentation, représente une tétration répétée ; elle est suivie d'une autre opération (hexatation) pour une pentation répétée, et ainsi de suite.

La fonction d'Ackermann, notée $latex A(n)$, est ce que vous obtenez lorsque vous montez d'un échelon sur cette échelle d'opérations à chaque arrêt sur la droite numérique : $latex A(1) = 1 + 1$, $latex A (2) = 2 × 2$, $latex A(3) = 3^3$, $latex A(4)=4 uparrowuparrow 4=4^{4^{4^4}}$, et ainsi de suite. Le nombre de chiffres dans $latex A(4)$ est lui-même un nombre colossal approximativement égal à 1 quinquagintillion — c'est le nom fantaisiste et rarement nécessaire pour un 1 suivi de 153 zéros. "Ne vous inquiétez pas pour Ackermann de 5", a conseillé Javier Esparça, informaticien à l'Université technique de Munich.

Les résultats de Leroux et Schmitz laissent un grand écart entre les limites inférieure et supérieure : la complexité précise du problème d'accessibilité du VAS pourrait se situer à l'une ou l'autre des extrémités de la plage ou n'importe où entre les deux. Czerwiński n'avait pas l'intention de laisser cet écart subsister. "Nous avons continué à travailler là-dessus parce qu'il était clair que c'était la chose la plus importante que nous ayons jamais faite dans notre vie", a-t-il déclaré.

La percée finale a eu lieu en 2021, alors que Czerwiński conseillait un étudiant de deuxième année nommé Łukasz Orlikowski. Il a assigné à Orlikowski une variante simple du problème pour le mettre au courant, et le travail d'Orlikowski les a aidés à développer une nouvelle technique qui s'appliquait également au problème général d'accessibilité. Cela leur a permis de augmenter la limite inférieure sensiblement - jusqu'à la limite supérieure d'Ackermann de Leroux et Schmitz. Travaillant de façon indépendante, Leroux a obtenu un résultat équivalent Autour du même moment.

Enfin, les chercheurs ont cerné la véritable complexité du problème d’accessibilité. La limite inférieure de Czerwiński, Orlikowski et Leroux a montré qu'il existe une séquence de systèmes d'addition de vecteurs progressivement plus grands dans lesquels le chemin le plus court entre deux états croît proportionnellement à la fonction d'Ackermann. La limite supérieure de Leroux et Schmitz a montré que le problème de l'accessibilité ne peut pas être plus complexe que cela – peu de consolation pour quiconque espère une procédure pratique infaillible pour le résoudre. C'est une illustration frappante de la subtilité de problèmes informatiques apparemment simples.

Jamais fini

Les chercheurs ont continué à étudier le problème d’accessibilité du VAS après avoir déterminé sa complexité exacte, car de nombreuses variantes de la question restent sans réponse. Les limites supérieures et inférieures d'Ackermann, par exemple, ne font pas de distinction entre les différentes manières d'augmenter n, comme augmenter la dimensionnalité des vecteurs ou augmenter le nombre de transitions autorisées.

Récemment, Czerwiński et ses collègues ont progrès accomplis démêler ces effets distincts en étudiant la rapidité avec laquelle la complexité peut augmenter dans les variantes de systèmes d'addition de vecteurs à dimensionnalité fixe. Mais il reste encore beaucoup à faire : même en trois dimensions, où les systèmes d'addition de vecteurs sont faciles à visualiser, la complexité exacte du problème d'accessibilité reste inconnue.

"D'une certaine manière, c'est tout simplement embarrassant pour nous", a déclaré Mazowiecki.

Les chercheurs espèrent qu’une meilleure compréhension de cas relativement simples les aidera à développer de nouveaux outils pour étudier d’autres modèles de calcul plus élaborés que les systèmes d’addition vectorielle. Actuellement, nous ne savons presque rien de ces modèles plus élaborés.

"Je considère cela comme faisant partie d'une quête très fondamentale pour comprendre la calculabilité", a déclaré Zetzsche.

Quanta mène une série d’enquêtes pour mieux servir notre public. Prenez notre enquête auprès des lecteurs en informatique et vous serez inscrit pour gagner gratuitement Quanta marchandise.