Algorithme galactique

Il existe plusieurs algorithmes connus ayant un comportement asymptotique, mais uniquement sur des problèmes peu pratiques :

• Multiplication d'entiers : un algorithme mis au point en 2019 par David Harvey et Joris van der Hoeven permet d'effectuer une multiplication d'entiers avec une complexité en O(n log n) mais celui-ci n'est efficace que pour des nombres supérieurs à 7,13×10³⁸, ce qui est inutilisable en pratique[5].
• multiplication matricielle. La première amélioration par rapport à la multiplication par force brute, O(N³), est l'algorithme de Strassen, un algorithme récursif qui est O(N^2,807). Cet algorithme n'est pas galactique et est utilisé dans la pratique. L’algorithme de Coppersmith-Winograd et ses successeurs légèrement meilleurs, en O(N^2,373), sont d’autres extensions de cette théorie, qui font appel à la théorie des groupes sophistiquée. Celles-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 rapide de matrices rendent généralement ces algorithmes inutilisables." ;
• le problème consistant à décider si un graphe G contient H en tant que mineur est NP-complet en général, mais lorsque H est fixe, il peut être résolu en temps polynomial. Le temps d'exécution pour tester si H est mineur de G dans ce cas est O(n²)[6] où n est le nombre de sommets dans G et la grande notation O masque une constante qui dépend superexponentiellement de H. La constante est supérieure à ${\displaystyle c>2\uparrow \uparrow (2\uparrow \uparrow (2\uparrow \uparrow (h/2)))}$ (en utilisant la notation des puissances itérées de Knuth ), et où h est le nombre de sommets dans H[7] ;
• pour les cryptographes, une « collision » cryptographique est plus rapide qu'une attaque par force brute, c'est-à-dire qu'elle effectue un décryptage d'essai pour chaque clé possible dans l'ordre. Dans de nombreux cas, même s’il s’agit des méthodes les plus connues, elles sont encore impossibles avec la technologie actuelle. Un exemple est la meilleure attaque connue contre AES 128 bits, qui ne nécessite que 2¹²⁶ opérations[8]. Bien qu’elles soient impraticables, les attaques théoriques peuvent parfois donner un aperçu des schémas de vulnérabilité ;
• il existe un algorithme unique appelé « recherche de Hutter » qui peut résoudre tout problème bien défini dans un temps asymptotiquement optimal, à moins de réserves. Cependant, ses constantes cachées dans le temps d'exécution sont si grandes qu'il ne serait jamais pratique pour quoi que ce soit[9] - [10].

• (en) Cet article est partiellement ou en totalité issu de l’article de Wikipédia en anglais intitulé « Galactic algorithm » (voir la liste des auteurs).