Algoritmo galáctico

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:^[1]

Esto por sí solo podría ser importante y, a menudo, es una gran razón para encontrar tales algoritmos. Por ejemplo, si mañana hubiera un descubrimiento que mostrara que hay un algoritmo de factorización con un límite de tiempo enorme pero demostrablemente polinomial, eso cambiaría nuestras creencias sobre la factorización. Es posible que el algoritmo nunca se use, pero sin duda daría forma a la investigación futura sobre la factorización.

De manera similar, un hipotético algoritmo ${\displaystyle O{\bigl (}n^{2^{100}}{\bigr )}}$ 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.^[2]

Un ejemplo de un algoritmo galáctico es la forma más rápida conocida de multiplicar dos números,^[3] que se basa en una transformada de Fourier de 1729 dimensiones.^[4] 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.^[5] 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".^[4]

La primera mejora sobre la multiplicación por fuerza bruta, ${\displaystyle O(n^{3})}$ es el algoritmo de Strassen, un algoritmo recursivo que es ${\displaystyle 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 ${\displaystyle 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".^[6]

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 ${\displaystyle n}$ bits y luego decodificar encontrando la palabra de código más cercana. Si se elige ${\displaystyle n}$ lo suficientemente grande, supera cualquier código existente y puede acercarse arbitrariamente a la capacidad del canal. Desafortunadamente, cualquier ${\displaystyle n}$ lo suficientemente grande como para vencer a los códigos existentes tampoco es práctico.^[7] 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.^[8]

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

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 ${\displaystyle 2^{126}}$ operaciones.^[11] A pesar de ser poco prácticos, los sistemas de desencriptado teóricos a veces pueden proporcionar información sobre los patrones de vulnerabilidad.

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 ${\displaystyle 10^{-34}}$ por ciento.^[12] 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".^[13]

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.^[14][15] 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.

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.^[16] 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.^[17]