Algorithme galactique : théoriquement optimal, jamais utilisé en pratique (fr)

Un algorithme galactique est un algorithme asymptotiquement plus rapide que tous ses concurrents, mais uniquement à partir de tailles de données si astronomiques qu’il n’est jamais utilisé en pratique. Parmi les exemples : la multiplication d’entiers en O(n log n) de Harvey et van der Hoeven (efficace seulement au-delà de 7,13×10³⁸ chiffres) ou l’algorithme de Coppersmith-Winograd pour la multiplication matricielle en O(N^2.373). Malgré leur inutilité pratique, ces algorithmes font progresser la théorie de la complexité et peuvent invalider des conjectures établies.