Algoritmo galáctico

Un algoritmo galáctico es aquel que supera a cualquier otro algoritmo para problemas que son suficientemente grandes, pero cuando "suficientemente grande" es tan grande que el algoritmo nunca se usa en la práctica. Los algoritmos galácticos fueron nombrados así por Richard Lipton y Ken Regan, haciendo alusión a que "nunca se utilizarán en ninguno de los conjuntos de datos meramente terrenales que se pudieran manejar aquí en la Tierra".

Posibles casos de uso

Incluso si nunca se usan en la práctica, los algoritmos galácticos aún pueden contribuir a la informática:

• Un algoritmo, incluso si no es práctico, puede mostrar nuevas técnicas que finalmente pueden usarse para crear otros algoritmos prácticos.
• La potencia computacional disponible puede alcanzar el punto de desarrollo necesario, de modo que un algoritmo que antes no era práctico llegue a serlo.
• Un algoritmo poco práctico aún puede demostrar que se pueden lograr los límites conjeturados, o que los límites propuestos son incorrectos y, por lo tanto, avanzar en la teoría de los algoritmos. Como dice Lipton:

De manera similar, un hipotético algoritmo $O\left(n^{2^{100}}\right)$ grande, pero polinomial, capaz de abordar el problema de satisfacibilidad booleana, aunque inutilizable en la práctica, resolvería la cuestión de P frente a NP, considerado el problema abierto más importante en informática y uno de los problemas del milenio.

Ejemplos

Multiplicación de enteros

Un ejemplo de un algoritmo galáctico es la forma más rápida conocida de multiplicar dos números, que se basa en una transformada de Fourier de 1729 dimensiones. Esto significa que no alcanzará su eficiencia indicada hasta que los números tengan al menos 2¹⁷²⁹¹² bits (al menos 10¹⁰³⁸ dígitos), que es mucho más grande que la cantidad de átomos en el universo conocido. Así que este algoritmo nunca se usa en la práctica. Sin embargo, también muestra por qué los algoritmos galácticos pueden ser útiles. Uno de los autores afirma: "Tenemos la esperanza de que, con más mejoras, el algoritmo pueda volverse práctico para números con solo miles de millones o billones de dígitos".

Multiplicación de matrices

La primera mejora sobre la multiplicación por fuerza bruta, $O(n^3)$ es el algoritmo de Strassen, un algoritmo recursivo que es $O(n^{2.807})$. Este algoritmo no es galáctico y se usa en la práctica. Otras extensiones del algoritmo, que utilizan una teoría de grupos sofisticada, son el algoritmo de Coppersmith–Winograd y sus sucesores ligeramente mejores, que ofrecen $O(n^{2.373})$. Estos últimos algoritmos son galácticos: "Sin embargo, enfatizamos que tales mejoras son solo de interés teórico, ya que las enormes constantes involucradas en la complejidad de la multiplicación rápida de matrices generalmente hacen que estos algoritmos no sean prácticos".

Capacidad de un canal de comunicación

Claude Shannon ideó un código simple pero poco práctico que podría alcanzar la capacidad de un canal de comunicación. Requiere asignar una palabra de código aleatoria a cada posible mensaje de $n$ bits y luego decodificar encontrando la palabra de código más cercana. Si se elige $n$ lo suficientemente grande, supera cualquier código existente y puede acercarse arbitrariamente a la capacidad del canal. Desafortunadamente, cualquier $n$ lo suficientemente grande como para vencer a los códigos existentes tampoco es práctico. Estos códigos, aunque nunca se usaron, inspiraron décadas de investigación en algoritmos más prácticos que hoy en día pueden lograr tasas arbitrariamente cercanas a la capacidad del canal.

Sub-grafos

El problema de decidir si un grafo $G$ contiene $H$ como menor es NP-completo en general, pero donde $H$ es fijo, se puede resolver en tiempo polinomial. El tiempo de ejecución para probar si $H$ es un menor de $G$ en este caso es $O(n^2)$, donde $n$ es el número de vértices en $G$ y la notación de la gran O oculta una constante que depende superexponencialmente de $H$. La constante es mayor que $2\uparrow \uparrow (2\uparrow \uparrow (2\uparrow \uparrow (h/2)))$ en la notación flecha de Knuth, donde $h$ es el número de vértices en $H$. Incluso el caso de $h=4$ no puede calcularse razonablemente, ya que la constante es mayor que $\genfrac{}{}{0ex}{}{}{}\genfrac{}{}{0ex}{}{\underbrace{2^{2^{{\cdot }^{{\cdot }^2}}}}}{n}$ con n = 65536.

Desencriptado

Para los criptógrafos, una "rotura" del código es algo más rápida que un ataque de fuerza bruta (es decir, realizar una decodificación de prueba para cada clave posible). En muchos casos, aunque son los métodos más conocidos, siguen siendo inviables con la tecnología actual. Un ejemplo es el mejor ataque conocido contra el sistema AES de 128 bits, que solo realiza $2^{126}$ operaciones. A pesar de ser poco prácticos, los sistemas de desencriptado teóricos a veces pueden proporcionar información sobre los patrones de vulnerabilidad.

Problema del viajante

Durante varias décadas, la aproximación más conocida al problema del viajante en un espacio métrico fue el muy simple algoritmo de Christofides, que producía un camino como máximo un 50% más largo que el óptimo (muchos otros algoritmos "generalmente" podrían hacerlo mucho mejor, pero es probable que no lo hagan). En 2020, se descubrió un algoritmo más nuevo y mucho más complejo que puede superar esto en un $10^{-34}$ por ciento. Aunque nadie cambiará jamás a este algoritmo por su muy leve mejora en el peor de los casos, todavía se considera importante porque "esta minúscula mejora rompe tanto un atasco teórico como psicológico".

Búsqueda de Hutter

Un solo algoritmo, la "búsqueda de Hutter", puede resolver cualquier problema bien definido en un tiempo asintóticamente óptimo, salvo en algunas circunstancias concretas. Funciona buscando a través de todos los algoritmos posibles (por tiempo de ejecución), mientras busca simultáneamente todas las pruebas posibles (por longitud de la prueba), y determinando además una prueba de la corrección de cada algoritmo. Dado que la prueba de corrección es de tamaño finito, "solo" agrega una constante y no afecta el tiempo de ejecución asintótico. Sin embargo, esta constante es tan grande que el algoritmo es totalmente impracticable. Por ejemplo, si la prueba más corta de corrección de un algoritmo dado tiene 1000 bits, la búsqueda examinará primero al menos 2⁹⁹⁹ de otras pruebas potenciales.

Optimización

Se ha demostrado que un algoritmo de recocido simulado, cuando se usa con un programa de enfriamiento logarítmico, encuentra el óptimo global de cualquier problema de optimización. Sin embargo, tal programa de enfriamiento da como resultado tiempos de ejecución totalmente impracticables y nunca se usa. Sin embargo, saber que este algoritmo ideal existe ha llevado a variantes prácticas que son capaces de encontrar soluciones muy buenas (aunque no probablemente óptimas) a problemas de optimización complejos.