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 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, peut montrer de nouvelles techniques pouvant éventuellement être utilisées pour créer des algorithmes plus efficaces ; * la puissance des ordinateurs peuvent rattraper la defaillance, 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( N2100 ) 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.