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,[1] 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".
Incluso si nunca se usan en la práctica, los algoritmos galácticos aún pueden contribuir a la informática: De manera similar, un hipotético algoritmo
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.
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.
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
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.
bits y luego decodificar encontrando la palabra de código más cercana.
lo suficientemente grande, supera cualquier código existente y puede acercarse arbitrariamente a la capacidad del canal.
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.
es fijo, se puede resolver en tiempo polinomial.
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
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).
[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.
Sin embargo, esta constante es tan grande que el algoritmo es totalmente impracticable.
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.