Un "algoritmo galáctico" es un algoritmo con un rendimiento teórico excepcional, pero que no se utiliza en la práctica debido a limitaciones reales. El término fue acuñado por Richard Lipton y Ken Regan, quienes bromeaban sobre que estos algoritmos nunca se aplicarían a conjuntos de datos terrestres.
La clave reside en la asintótica. Mientras que la notación 'Big O' describe cómo el tiempo de ejecución de un algoritmo escala con el tamaño de la entrada (por ejemplo, O(n) significa que el tiempo crece linealmente con 'n'), los algoritmos galácticos tienen constantes ocultas dentro de esa notación que son tan grandes que el algoritmo se vuelve ineficiente incluso para entradas extremadamente grandes. En otras palabras, la ganancia teórica en rendimiento es eclipsada por la complejidad inherente del algoritmo.
Un ejemplo claro es la multiplicación de enteros. Existe un algoritmo para multiplicar dos números que utiliza una transformada de Fourier de 1729 dimensiones. Su complejidad asintótica es impresionante, pero el número de operaciones necesarias es tan elevado que es más lento que los métodos de multiplicación convencionales, incluso para números con miles de millones de dígitos. Sin embargo, el desarrollo de este algoritmo ha impulsado la investigación en técnicas de multiplicación más eficientes.
Otro caso lo encontramos en las pruebas de primalidad. El algoritmo de primality de AKS es teóricamente sólido y tiene un tiempo de ejecución polinómico, pero es mucho más lento que otros métodos prácticos como la prueba de Miller-Rabin. Aunque AKS no se usa en la práctica, su existencia demuestra que ciertos límites teóricos son alcanzables, lo que puede influir en la investigación.
Los algoritmos galácticos no son inútiles. Pueden: 1) Inspirar nuevas técnicas que se apliquen en algoritmos prácticos; 2) Convertirse en prácticos con el avance de la potencia computacional; y 3) Validar o refutar conjeturas teóricas sobre los límites de los algoritmos. Por ejemplo, un algoritmo para resolver el problema de la satisfactibilidad booleana (SAT) con un tiempo de ejecución polinómico, aunque inútil en la práctica, resolvería el famoso problema P versus NP. Incluso las “rupturas” criptográficas, ataques teóricos más rápidos que la fuerza bruta, aunque actualmente inviables, pueden revelar vulnerabilidades y guiar la investigación en criptografía.
En resumen, los algoritmos galácticos son experimentos mentales que empujan los límites de la informática teórica, aunque rara vez se implementan en el mundo real.