Algorithme galactique

Carte Commune · n° 256177

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 101038 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...

Lire sur Wikipédia