Algoritmo galáctico

Clasificación de algoritmos

Un algoritmo galáctico es un algoritmo con un rendimiento teórico ( asintótico ) sin precedentes , pero que no se utiliza debido a limitaciones prácticas. Las razones típicas son que las mejoras de rendimiento solo aparecen para problemas que son tan grandes que nunca ocurren, o la complejidad del algoritmo supera una mejora relativamente pequeña en el rendimiento. Los algoritmos galácticos fueron denominados así por Richard Lipton y Ken Regan ^[1] porque nunca se utilizarán en ningún conjunto de datos de la Tierra.

Posibles casos de uso

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

• Un algoritmo, incluso si no es práctico, puede mostrar nuevas técnicas que eventualmente puedan usarse para crear algoritmos prácticos.
• La potencia computacional disponible puede alcanzar el punto de cruce, de modo que un algoritmo previamente impráctico se vuelva práctico.
• Un algoritmo poco práctico puede demostrar que se pueden alcanzar los límites conjeturados o que los límites propuestos son erróneos y, por lo tanto, hacer avanzar la teoría de algoritmos. Como afirma Lipton: ^[1]

  Esto por sí solo podría ser importante y, a menudo, es una gran razón para encontrar dichos algoritmos. Por ejemplo, si mañana se descubriera que existe un algoritmo de factorización con un límite temporal enorme pero demostrablemente polinómico, eso cambiaría nuestras creencias sobre la factorización. Es posible que el algoritmo nunca se utilice, pero sin duda dará forma a la investigación futura sobre factorización.

  De manera similar, un algoritmo hipotético para el problema de satisfacibilidad booleano con un límite de tiempo grande pero polinomial, como , aunque inutilizable en la práctica, resolvería el problema P versus NP , considerado el problema abierto más importante en informática y uno de los problemas del Premio del Milenio . ^[2] ${\displaystyle \Theta {\bigl (}n^{2^{100}}{\bigr )}}$

Ejemplos

Multiplicación de enteros

Un ejemplo de 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] Necesita operaciones de bits, pero como las constantes ocultas por la notación O grande son grandes, nunca se usa en la práctica. Sin embargo, también muestra por qué los algoritmos galácticos aún pueden ser útiles. Los autores afirman: "tenemos la esperanza de que con más refinamientos, el algoritmo pueda volverse práctico para números con solo miles de millones o billones de dígitos". ^[4] ${\displaystyle O(n\log n)}$

Multiplicación de matrices

La primera mejora con respecto a la multiplicación de matrices por fuerza bruta (que necesita multiplicaciones) fue el algoritmo de Strassen : un algoritmo recursivo que necesita multiplicaciones. Este algoritmo no es galáctico y se utiliza en la práctica. Otras extensiones de este algoritmo, que utilizan una teoría de grupos sofisticada, son el algoritmo Coppersmith-Winograd y sus sucesores ligeramente mejores, que necesitan multiplicaciones. Estos son galácticos: "No obstante, subrayamos que estas mejoras son sólo de interés teórico, ya que las enormes constantes implicadas en la complejidad de la multiplicación rápida de matrices suelen hacer que estos algoritmos sean poco prácticos". ^[5] ${\displaystyle O(n^{3})}$ ${\displaystyle O(n^{2.807})}$ ${\displaystyle O(n^{2.373})}$

Capacidad del canal de comunicación

Claude Shannon mostró un código simple pero asintóticamente óptimo que puede alcanzar la capacidad teórica de un canal de comunicación . Requiere asignar una palabra de código aleatoria a cada mensaje de 128 bits posible, luego decodificar encontrando la palabra de código más cercana. Si se elige lo suficientemente grande, esto supera a cualquier código existente y puede acercarse arbitrariamente a la capacidad del canal. Desafortunadamente, cualquier código lo suficientemente grande como para superar los códigos existentes también es completamente impráctico. ^[6] Estos códigos, aunque nunca se usaron, inspiraron décadas de investigación en algoritmos más prácticos que hoy pueden lograr tasas arbitrariamente cercanas a la capacidad del canal. ^[7] ${\displaystyle n}$ ${\displaystyle n}$ ${\displaystyle n}$

Subgrafos

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

Desgloses criptográficos

En la jerga criptográfica , una "ruptura" es cualquier ataque que, en teoría, sea más rápido que la fuerza bruta , es decir, que realice un descifrado de prueba para cada clave posible. En muchos sistemas criptográficos, las rupturas son conocidas, pero siguen siendo prácticamente inviables con la tecnología actual. Un ejemplo es el mejor ataque conocido contra AES de 128 bits , que solo requiere operaciones. ^[10] A pesar de ser poco prácticas, las rupturas teóricas pueden proporcionar información sobre patrones de vulnerabilidad y, a veces, llevar al descubrimiento de rupturas explotables. ${\displaystyle 2^{126}}$

Problema del viajante de comercio

Durante varias décadas, la aproximación más conocida al problema del viajante de comercio en un espacio métrico fue el algoritmo de Christofides, muy simple , que producía un camino como máximo un 50 % más largo que el óptimo. (Muchos otros algoritmos normalmente podrían hacerlo mucho mejor, pero no podrían hacerlo de manera demostrable). En 2020, se descubrió un algoritmo más nuevo y mucho más complejo que puede superarlo en un porcentaje. ^[11] Aunque nadie cambiará nunca 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 uno psicológico". ^[12] ${\displaystyle 10^{-34}}$

Búsqueda de Hutter

Un único algoritmo, la "búsqueda de Hutter", puede resolver cualquier problema bien definido en un tiempo asintóticamente óptimo, salvo algunas salvedades. Funciona buscando entre todos los algoritmos posibles (por tiempo de ejecución), mientras que simultáneamente busca entre todas las pruebas posibles (por longitud de la prueba), buscando una prueba de corrección para 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 completamente impráctico. ^{[13] [14]} Por ejemplo, si la prueba de corrección más corta de un algoritmo dado tiene 1000 bits de longitud, la búsqueda examinará al menos otras ²⁹⁹⁹ pruebas potenciales primero.

La búsqueda de Hutter está relacionada con la inducción de Solomonoff , que es una formalización de la inferencia bayesiana. Todas las teorías computables (tal como las implementan los programas) que describen perfectamente las observaciones anteriores se utilizan para calcular la probabilidad de la siguiente observación, y se da más peso a las teorías computables más cortas. Una vez más, la búsqueda de todas las explicaciones posibles hace que este procedimiento sea galáctico.

Mejoramiento

Se ha demostrado que el recocido simulado , cuando se utiliza con un programa de enfriamiento logarítmico, permite encontrar el óptimo global de cualquier problema de optimización. Sin embargo, un programa de enfriamiento de este tipo da como resultado tiempos de ejecución totalmente imprácticos y nunca se utiliza. ^[15] Sin embargo, saber que existe este algoritmo ideal ha llevado a variantes prácticas que pueden encontrar soluciones muy buenas (aunque no demostrablemente óptimas) para problemas de optimización complejos. ^[16]

Árboles de expansión mínimos

El algoritmo MST de tiempo lineal esperado es capaz de descubrir el árbol de expansión mínimo de un gráfico en , donde es el número de aristas y es el número de nodos del gráfico. ^[17] Sin embargo, el factor constante que está oculto por la notación Big O es lo suficientemente grande como para hacer que el algoritmo sea poco práctico. Una implementación está disponible públicamente ^[18] y dadas las constantes de implementación estimadas experimentalmente, solo sería más rápido que el algoritmo de Borůvka para gráficos en los que . ^[19] ${\displaystyle O(m+n)}$ ${\displaystyle m}$ ${\displaystyle n}$ ${\displaystyle m+n>9\cdot 10^{151}}$

Tablas hash

Los investigadores han descubierto un algoritmo que logra el mejor rendimiento asintótico posible ^[20] en términos de equilibrio entre tiempo y espacio. ^[21] Pero sigue siendo puramente teórico: "A pesar de la eficiencia sin precedentes de la nueva tabla hash, es poco probable que nadie intente construirla en un futuro próximo. Es demasiado complicada de construir" ^[22] y "en la práctica, las constantes realmente importan. En el mundo real, un factor de 10 es el final del juego". ^[23]

Referencias

1. Lipton, Richard J. ; Regan, Kenneth W. (2013). "David Johnson: Algoritmos galácticos". Personas, problemas y pruebas: ensayos de la carta perdida de Gödel: 2010 . Heidelberg: Springer Berlin. págs. 109–112. ISBN 9783642414220.
2. Fortnow, L. (2009). "El estado del problema P versus NP" (PDF) . Comunicaciones de la ACM . 52 (9): 78–86. doi :10.1145/1562164.1562186. S2CID  5969255.
3. David, Harvey; Hoeven, Joris van der (marzo de 2019). "Multiplicación de enteros en el tiempo O (n log n)". HAL . hal-02070778.
4. Harvey, David (9 de abril de 2019). "Hemos encontrado una forma más rápida de multiplicar números muy grandes". The Conversation . Consultado el 9 de marzo de 2023 .
5. Le Gall, F. (2012), "Algoritmos más rápidos para la multiplicación de matrices rectangulares", Actas del 53.º Simposio anual IEEE sobre fundamentos de la informática (FOCS 2012) , págs. 514-523, arXiv : 1204.1111 , doi : 10.1109/FOCS.2012.80, ISBN 978-0-7695-4874-6, S2CID2410545 ​
6. Larry Hardesty (19 de enero de 2010). "Explicación: el límite de Shannon". Oficina de noticias del MIT.
7. "Códigos de aproximación a la capacidad (Capítulo 13 de Principios de la comunicación digital II)" (PDF) . MIT OpenCourseWare . 2005.
8. Kawarabayashi, Ken-ichi; Kobayashi, Yusuke; Reed, Bruce (2012). "El problema de los caminos disjuntos en tiempo cuadrático". Journal of Combinatorial Theory . Serie B. 102 (2): 424–435. doi : 10.1016/j.jctb.2011.07.004 .
9. Johnson, David S. (1987). "La columna de NP-completitud: una guía en curso (edición 19)". Journal of Algorithms . 8 (2): 285–303. CiteSeerX 10.1.1.114.3864 . doi :10.1016/0196-6774(87)90043-5. 
10. Biaoshuai Tao y Hongjun Wu (2015). Seguridad de la información y privacidad . Apuntes de clase en informática. Vol. 9144. Págs. 39-56. doi :10.1007/978-3-319-19962-7_3. ISBN 978-3-319-19961-0.
11. Anna R. Karlin; Nathan Klein; Shayan Oveis Gharan (1 de septiembre de 2020). "Un algoritmo de aproximación (ligeramente) mejorado para TSP métrico". arXiv : 2007.01409 [cs.DS].
12. Klarreich, Erica (8 de octubre de 2020). "Los científicos informáticos rompen el récord de ventas de los vendedores ambulantes". Revista Quanta .
13. Hutter, Marcus (14 de junio de 2002). "El algoritmo más rápido y más corto para todos los problemas bien definidos". arXiv : cs/0206022 .
14. Gagliolo, Matteo (20 de noviembre de 2007). "Búsqueda universal". Scholarpedia . 2 (11): 2575. Código bibliográfico : 2007SchpJ...2.2575G. doi : 10.4249/scholarpedia.2575 . ISSN  1941-6016.
15. Liang, Faming; Cheng, Yichen; Lin, Guang (2014). "Recocido de aproximación estocástica simulado para optimización global con un programa de enfriamiento de raíz cuadrada". Revista de la Asociación Estadounidense de Estadística . 109 (506): 847–863. doi :10.1080/01621459.2013.872993. S2CID  123410795.
16. Ingber, Lester (1993). "Recocido simulado: práctica versus teoría". Modelado matemático y computacional . 18 (11): 29–57. CiteSeerX 10.1.1.15.1046 . doi : 10.1016/0895-7177(93)90204-C . 
17. Karger, David R.; Klein, Philip N.; Tarjan, Robert E. (1995-03-01). "Un algoritmo de tiempo lineal aleatorio para encontrar árboles de expansión mínimos". Revista de la ACM . 42 (2): 321–328. doi : 10.1145/201019.201022 . ISSN  0004-5411.
18. Thiesen, Francisco. "Una implementación en C++ para un algoritmo de árbol de expansión mínimo en tiempo lineal esperado (verificación del árbol de expansión mínimo de Karger-Klein-Tarjan + Hagerup como subrutina)". GitHub . Consultado el 19 de noviembre de 2022 .
19. Geiman Thiesen, Francisco. "Árboles de expansión mínimos de tiempo lineal esperados". franciscothiesen.github.io . Consultado el 13 de noviembre de 2022 .
20. Tianxiao Li, Jingxun Liang, Huacheng Yu y Renfei Zhou. "Límites inferiores ajustados de la sonda celular para diccionarios dinámicos y sucintos" (PDF) .{{cite web}}: CS1 maint: varios nombres: lista de autores ( enlace )
21. Bender, Michael; Farach-Colton, Martin; Kuszmaul, John; Kuszmaul, William; Mingmou, Liu (4 de noviembre de 2021). "Sobre el equilibrio óptimo entre tiempo y espacio para las tablas hash". arXiv : 2111.00602 [cs].
22. "Los científicos encuentran el equilibrio óptimo entre el almacenamiento de datos y el tiempo". 8 de febrero de 2024.
23. William Kuszmaul, citado en "Los científicos encuentran el equilibrio óptimo entre el almacenamiento de datos y el tiempo". 8 de febrero de 2024.