Algorithme galactique

Un algorithme galactique est un algorithme de résolution d'un problème qui est plus rapide que tous les autres algorithmes quand le problème est suffisamment grand, mais dans le cas où « suffisamment grand » est tellement grand que l’algorithme n’est en pratique jamais utilisé. Les algorithmes galactiques ont été nommés ainsi par Richard Lipton et Ken Regan parce qu'ils ne seront jamais utilisés pour aucun ensemble de données trouvé sur Terre.

Un exemple d'algorithme galactique est l'algorithme pour multiplier deux nombres qui est basé sur une transformée de Fourier à 1 729 dimensions^,. Cela signifie qu’elle ne sera pas la plus rapide tant que les nombres n’auront pas au moins 10^10³⁸ chiffres, (considérablement) plus de chiffres qu’il n’y a d’atomes dans l’univers. Donc, cet algorithme n'est jamais utilisé dans la pratique.

Malgré le fait qu’ils ne seront jamais utilisés, les algorithmes galactiques peuvent néanmoins contribuer à l'informatique :

un algorithme, même s’il n’est pas utilisable, peut montrer de nouvelles techniques pouvant éventuellement être utilisées pour créer des algorithmes plus efficaces ;
la puissance des ordinateurs peut rattraper la défaillance, de sorte qu'un algorithme auparavant peu pratique le devient ;
un algorithme inutilisable peut toujours démontrer que des bornes conjecturées peuvent être obtenues, ou alternativement, montrer que les limites conjecturées sont fausses. Comme le dit Lipton, « En soi cet argument est suffisant pour donner d'excellentes raisons de trouver de tels algorithmes. Par exemple, s'il existait demain une découverte montrant qu'il existait un algorithme de factorisation avec une limite de temps énorme mais polynomiale, cela changerait nos connaissances sur la factorisation. L’algorithme pourrait ne jamais être utilisé, mais déterminerait certainement les recherches futures en factorisation. » De même, un algorithme O( N^2¹⁰⁰ ) pour le problème SAT, bien qu'inutilisable en pratique, réglerait le problème P = NP, qui est le problème ouvert le plus important en informatique. Un effet pratique immédiat serait l'obtention par le découvreur d'un prix d'un million de dollars par le Clay Mathematics Institute.

Exemples

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.
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²) où n est le nombre de sommets dans G et la notation O (« grand O ») masque une constante qui dépend superexponentiellement de H. La constante est supérieure à $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 ;
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. 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^,.

Notes et références

(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).

↑ Lipton, Richard J., and Kenneth W. Regan, People, Problems, and Proofs, Heidelberg, Springer Berlin, 2013, 109–112 p., « David Johnson: Galactic Algorithms »
1 2 (en) David Harvey et Joris Van Der Hoeven, « Integer multiplication in time O(n log n) », HAL,‎ mars 2019 (lire en ligne)
↑ David Harvey, « We've found a quicker way to multiply really big numbers », Phys.org, 10 avril 2019
↑ Fortnow, L., « The status of the P versus NP problem », Communications of the ACM, vol. 52, n^o 9,‎ 2009, p. 78-86 (lire en ligne)
↑ Jean-Paul Delahaye, « L'efficacité trompeuse des algorithmes galactiques », Pour la Science, n^o 548,‎ juin 2023.
↑ Kawarabayashi, K. I., Kobayashi, Y., & Reed, B., « The disjoint paths problem in quadratic time », Journal of Combinatorial Theory, Series B, vol. 102, n^o 2,‎ 2012, p. 424-435
↑ Johnson, David S., « The NP-completeness column: An ongoing guide (edition 19) », Journal of Algorithms, vol. 8, n^o 2,‎ 1987, p. 285–303 (DOI 10.1016/0196-6774(87)90043-5)
↑ Biaoshuai Tao et Hongjun Wu, Information Security and Privacy, vol. 9144, coll. « Lecture Notes in Computer Science », 2015, 39–56 p. (ISBN 978-3-319-19961-0, DOI 10.1007/978-3-319-19962-7_3)
↑ Hutter, « The Fastest and Shortest Algorithm for All Well-Defined Problems », arXiv:cs/0206022,‎ 14 juin 2002 (lire en ligne)
↑ (en) Gagliolo, « Universal search », Scholarpedia, vol. 2, n^o 11,‎ 20 novembre 2007, p. 2575 (ISSN 1941-6016, DOI 10.4249/scholarpedia.2575, lire en ligne)

Bibliographie

Jean-Paul Delahaye, « L'efficacité trompeuse des algorithmes galactiques », Pour la science, n^o 548,‎ juin 2023, p. 80-85 (présentation en ligne)

Portail de l'informatique théorique

[1] Lipton, Richard J., and Kenneth W. Regan, People, Problems, and Proofs, Heidelberg, Springer Berlin, 2013, 109–112 p., « David Johnson: Galactic Algorithms »

[Harvey_Van-Der-Hoeven-2] 1 2 (en) David Harvey et Joris Van Der Hoeven, « Integer multiplication in time O(n log n) », HAL,‎ mars 2019 (lire en ligne)

[3] David Harvey, « We've found a quicker way to multiply really big numbers », Phys.org, 10 avril 2019

[4] Fortnow, L., « The status of the P versus NP problem », Communications of the ACM, vol. 52, n^o 9,‎ 2009, p. 78-86 (lire en ligne)

[5] Jean-Paul Delahaye, « L'efficacité trompeuse des algorithmes galactiques », Pour la Science, n^o 548,‎ juin 2023.

[kkr12-6] Kawarabayashi, K. I., Kobayashi, Y., & Reed, B., « The disjoint paths problem in quadratic time », Journal of Combinatorial Theory, Series B, vol. 102, n^o 2,‎ 2012, p. 424-435

[7] Johnson, David S., « The NP-completeness column: An ongoing guide (edition 19) », Journal of Algorithms, vol. 8, n^o 2,‎ 1987, p. 285–303 (DOI 10.1016/0196-6774(87)90043-5)

[:0-8] Biaoshuai Tao et Hongjun Wu, Information Security and Privacy, vol. 9144, coll. « Lecture Notes in Computer Science », 2015, 39–56 p. (ISBN 978-3-319-19961-0, DOI 10.1007/978-3-319-19962-7_3)

[9] Hutter, « The Fastest and Shortest Algorithm for All Well-Defined Problems », arXiv:cs/0206022,‎ 14 juin 2002 (lire en ligne)

[10] (en) Gagliolo, « Universal search », Scholarpedia, vol. 2, n^o 11,‎ 20 novembre 2007, p. 2575 (ISSN 1941-6016, DOI 10.4249/scholarpedia.2575, lire en ligne)