Algorithme galactique - Galactic algorithm

Un algorithme galactique est un algorithme qui surpasse tout autre algorithme pour des problèmes suffisamment grands, mais où « suffisamment grand » est si grand que l'algorithme n'est jamais utilisé dans la pratique. Les algorithmes galactiques ont été ainsi nommés par Richard Lipton et Ken Regan, car ils ne seront jamais utilisés sur aucun des ensembles de données purement terrestres que nous trouvons ici sur Terre.

Cas d'utilisation

Même s'ils ne sont jamais utilisés en pratique, les algorithmes galactiques peuvent tout de même contribuer à l'informatique :

Un algorithme, même s'il n'est pas pratique, peut montrer de nouvelles techniques qui peuvent éventuellement être utilisées pour créer des algorithmes pratiques.
La taille des ordinateurs peut rattraper le point de croisement, de sorte qu'un algorithme auparavant peu pratique devient pratique.
Un algorithme peu pratique peut toujours démontrer que des limites conjecturées peuvent être atteintes, ou que les limites proposées sont fausses, et ainsi faire avancer la théorie des algorithmes. Comme Lipton le déclare :
Cela seul pourrait être important et constitue souvent une excellente raison de trouver de tels algorithmes. Par exemple, si demain il y avait une découverte qui montrait qu'il existe un algorithme de factorisation avec une limite temporelle énorme mais prouvable polynomiale, cela changerait nos croyances sur la factorisation. L'algorithme pourrait ne jamais être utilisé, mais il façonnerait certainement les futures recherches sur l'affacturage.
De même, un algorithme pour le problème de satisfiabilité booléenne , bien qu'inutilisable en pratique, réglerait le problème P versus NP , le problème ouvert le plus important en informatique et l'un des problèmes du prix du millénaire . $O{\bigl (}n^{2^{100}}{\bigr )}$

Exemples

Multiplication d'entiers

Un exemple d'algorithme galactique est le moyen le plus rapide connu de multiplier deux nombres , qui est basé sur une transformée de Fourier à 1729 dimensions . Cela signifie qu'il n'atteindra pas son efficacité déclarée tant que les nombres n'auront pas au moins 2 ^{1729 ¹²} bits (au moins 10 ^{10 ³⁸} chiffres), ce qui est considérablement plus grand que le nombre d'atomes dans l'univers connu. Cet algorithme n'est donc jamais utilisé en pratique.

Multiplication matricielle

La première amélioration par rapport à la multiplication par force brute est l' algorithme de Strassen , un algorithme récursif qui est . Cet algorithme n'est pas galactique et est utilisé en pratique. D'autres extensions de ceci, utilisant la théorie des groupes sophistiquée, sont l' algorithme Coppersmith-Winograd et ses successeurs légèrement meilleurs, fournissant . Ceux-ci sont galactiques - "Nous soulignons néanmoins que de telles améliorations n'ont qu'un intérêt théorique, car les énormes constantes impliquées dans la complexité de la multiplication matricielle rapide rendent généralement ces algorithmes peu pratiques." ${\style d'affichage O(n^{3})}$ ${\style d'affichage O(n^{2.807})}$ ${\style d'affichage O(n^{2.373})}$

Capacité du canal de communication

Claude Shannon a montré un code simple mais peu pratique qui pouvait atteindre la capacité d'un canal de communication . Cela nécessite d'attribuer un mot de code aléatoire à chaque message de bit possible , puis de décoder en trouvant le mot de code le plus proche. Si est choisi suffisamment grand, cela bat n'importe quel code existant et peut se rapprocher arbitrairement de la capacité du canal. Malheureusement, tout assez grand pour battre les codes existants est également totalement impraticable. Ces codes, bien que jamais utilisés, ont inspiré des décennies de recherche sur des algorithmes plus pratiques qui peuvent aujourd'hui atteindre des débits arbitrairement proches de la capacité du canal. ${\style d'affichage n}$ ${\style d'affichage n}$ ${\style d'affichage n}$

Sous-graphiques

Le problème de décider si un graphe contient comme mineur est NP-complet en général, mais là où est fixé, il peut être résolu en temps polynomial. Le temps d'exécution pour tester si est un mineur de dans ce cas est , où est le nombre de sommets dans et la grande notation O cache une constante qui dépend de façon super exponentielle de . La constante est supérieure à (en utilisant la notation de flèche vers le haut de Knuth ), où est le nombre de sommets dans . Même pour les petits nombres tels que , la constante donne , un nombre avec 19729 chiffres décimaux. Pour , il ne peut pas raisonnablement calculer : , où la pièce est une tour électrique de 16 exemplaires sur 2, un nombre si grand que sa valeur exacte ne peut pas être pratiquement calculé. L'expression entière est une tour de puissance de tant d'exemplaires de 2. ${\style d'affichage G}$ ${\style d'affichage H}$ ${\style d'affichage H}$ ${\style d'affichage H}$ ${\style d'affichage G}$ ${\style d'affichage O(n^{2})}$ ${\style d'affichage n}$ ${\style d'affichage G}$ ${\style d'affichage H}$ $2\uparrow \uparrow (2\uparrow \uparrow (2\uparrow \uparrow (h/2)))$ ${\style d'affichage h}$ ${\style d'affichage H}$ ${\style d'affichage h=4}$ ${\style d'affichage 2^{65536}}$ ${\style d'affichage h=6}$ $2\uparrow \uparrow (2\uparrow \uparrow (2\uparrow \uparrow (6/2)))=2\uparrow \uparrow {\Bigl (}2^{\cdot ^{\cdot ^{2 }}}{\Grand )}$ $2^{\cdot ^{\cdot ^{2}}}$

Ruptures cryptographiques

Pour les cryptographes, une "rupture" cryptographique est quelque chose de plus rapide qu'une attaque par force brute - c'est-à-dire, effectuer un déchiffrement d'essai pour chaque clé possible. Dans de nombreux cas, même si ce sont les méthodes les plus connues, elles sont encore infaisables avec la technologie actuelle. Un exemple est la meilleure attaque connue contre AES 128 bits , qui ne prend que des opérations. Bien qu'elles soient peu pratiques, les ruptures théoriques peuvent parfois donner un aperçu des modèles de vulnérabilité. ${\style d'affichage 2^{126}}$

Problème de voyageur de commerce

Pendant plusieurs décennies, l'approximation la plus connue du problème du voyageur de commerce dans un espace métrique était l' algorithme très simple de Christofides qui produisait un chemin au plus 50 % plus long que l'optimum. (De nombreux autres algorithmes pourraient généralement faire beaucoup mieux, mais ne pouvaient pas le faire de manière prouvée.) En 2020, un algorithme plus récent et beaucoup plus complexe a été découvert qui peut battre ce pourcentage. Bien que personne ne passera jamais à cet algorithme pour sa très légère amélioration dans le pire des cas, il est toujours considéré comme important car « cette minuscule amélioration franchit à la fois un blocage théorique et psychologique ». $10^{-34}$

Recherche de hutter

Il existe un seul algorithme connu sous le nom de "recherche de Hutter" qui peut résoudre n'importe quel problème bien défini dans un temps asymptotiquement optimal, sauf quelques mises en garde. Cependant, ses constantes cachées dans le temps d'exécution sont si grandes qu'elles ne seraient jamais pratiques pour quoi que ce soit.

Languages

In other projects