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,^[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".

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

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,^[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^1729¹² bits (al menos 10^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]

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".^[6]

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

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})$ ,^[9] 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$ .^[10] Incluso el caso de $h=4$ no puede calcularse razonablemente, ya que la constante es mayor que ${\ \atop {\ }}{{\underbrace {2^{2^{\cdot ^{\cdot ^{2}}}}} } \atop 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.^[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.

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

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.^[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.

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

Referencias

↑ ^a ^b Lipton, Richard J., and Kenneth W. Regan (2013). «David Johnson: Galactic Algorithms». People, Problems, and Proofs. Heidelberg: Springer Berlin. pp. 109-112.
↑ Fortnow, L. (2009). «The status of the P versus NP problem». Communications of the ACM 52 (9): 78-86. S2CID 5969255. doi:10.1145/1562164.1562186.
↑ David, Harvey; Hoeven, Joris van der (March 2019). «Integer multiplication in time O(n log n)». HAL. hal-02070778.
↑ ^a ^b David Harvey (April 2019). «We've found a quicker way to multiply really big numbers». Phys.org.
↑ «We've found a quicker way to multiply really big numbers». Cita, de uno de los autores del algoritmo: "El nuevo algoritmo no es realmente práctico en su forma actual, porque la prueba dada en nuestro artículo solo funciona para números ridículamente grandes. Incluso si cada dígito se escribiera en un átomo de hidrógeno, no habría suficiente espacio disponible en el universo observable para escribirlos."
↑ Le Gall, F. (2012), «Faster algorithms for rectangular matrix multiplication», Proceedings of the 53rd Annual IEEE Symposium on Foundations of Computer Science (FOCS 2012), pp. 514-523, S2CID 2410545, arXiv:1204.1111, doi:10.1109/FOCS.2012.80 .
↑ Larry Hardesty (19 de enero de 2010). «Explained: The Shannon limit». MIT News Office.
↑ «Capacity-Approaching Codes».
↑ Kawarabayashi, K. I.; Kobayashi, Y.; Reed, B. (2012). «The disjoint paths problem in quadratic time». Journal of Combinatorial Theory, Series B 102 (2): 424-435. doi:10.1016/j.jctb.2011.07.004.
↑ Johnson, David S. (1987). «The NP-completeness column: An ongoing guide (edition 19)». Journal of Algorithms 8 (2): 285-303. doi:10.1016/0196-6774(87)90043-5. «citeseerx: 10.1.1.114.3864».
↑ Biaoshuai Tao; Hongjun Wu (2015). Information Security and Privacy. Lecture Notes in Computer Science 9144. pp. 39-56. ISBN 978-3-319-19961-0. doi:10.1007/978-3-319-19962-7_3.
↑ Anna R. Karlin; Nathan Klein; Shayan Oveis Gharan (2020-09-01). «A (Slightly) Improved Approximation Algorithm for Metric TSP». arXiv:2007.01409 [cs.DS].
↑ Klarreich, Erica (8 de octubre de 2020). «Computer Scientists Break Traveling Salesperson Record». Quanta Magazine.
↑ Hutter, Marcus (2002-06-14). «The Fastest and Shortest Algorithm for All Well-Defined Problems». arXiv:cs/0206022.
↑ Gagliolo, Matteo (20 de noviembre de 2007). «Universal search». Scholarpedia (en inglés) 2 (11): 2575. Bibcode:2007SchpJ...2.2575G. ISSN 1941-6016. doi:10.4249/scholarpedia.2575.
↑ Liang, Faming, Yichen Cheng, and Guang Lin (2014). «Simulated stochastic approximation annealing for global optimization with a square-root cooling schedule». Journal of the American Statistical Association 109 (506): 847-863. S2CID 123410795. doi:10.1080/01621459.2013.872993.
↑ Ingber, Lester (1993). «Simulated annealing: Practice versus theory». Mathematical and Computer Modelling 18 (11): 29-57. doi:10.1016/0895-7177(93)90204-C.

Datos: Q65072234

[seminal-1] Lipton, Richard J., and Kenneth W. Regan (2013). «David Johnson: Galactic Algorithms». People, Problems, and Proofs. Heidelberg: Springer Berlin. pp. 109-112.

[2] Fortnow, L. (2009). «The status of the P versus NP problem». Communications of the ACM 52 (9): 78-86. S2CID 5969255. doi:10.1145/1562164.1562186.

[3] David, Harvey; Hoeven, Joris van der (March 2019). «Integer multiplication in time O(n log n)». HAL. hal-02070778.

[quick-4] David Harvey (April 2019). «We've found a quicker way to multiply really big numbers». Phys.org.

[conv-5] «We've found a quicker way to multiply really big numbers». Cita, de uno de los autores del algoritmo: "El nuevo algoritmo no es realmente práctico en su forma actual, porque la prueba dada en nuestro artículo solo funciona para números ridículamente grandes. Incluso si cada dígito se escribiera en un átomo de hidrógeno, no habría suficiente espacio disponible en el universo observable para escribirlos."

[6] Le Gall, F. (2012), «Faster algorithms for rectangular matrix multiplication», Proceedings of the 53rd Annual IEEE Symposium on Foundations of Computer Science (FOCS 2012), pp. 514-523, S2CID 2410545, arXiv:1204.1111, doi:10.1109/FOCS.2012.80 .

[7] Larry Hardesty (19 de enero de 2010). «Explained: The Shannon limit». MIT News Office.

[8] «Capacity-Approaching Codes».

[kkr12-9] Kawarabayashi, K. I.; Kobayashi, Y.; Reed, B. (2012). «The disjoint paths problem in quadratic time». Journal of Combinatorial Theory, Series B 102 (2): 424-435. doi:10.1016/j.jctb.2011.07.004.

[10] Johnson, David S. (1987). «The NP-completeness column: An ongoing guide (edition 19)». Journal of Algorithms 8 (2): 285-303. doi:10.1016/0196-6774(87)90043-5. «citeseerx: 10.1.1.114.3864».

[:0-11] Biaoshuai Tao; Hongjun Wu (2015). Information Security and Privacy. Lecture Notes in Computer Science 9144. pp. 39-56. ISBN 978-3-319-19961-0. doi:10.1007/978-3-319-19962-7_3.

[12] Anna R. Karlin; Nathan Klein; Shayan Oveis Gharan (2020-09-01). «A (Slightly) Improved Approximation Algorithm for Metric TSP». arXiv:2007.01409 [cs.DS].

[13] Klarreich, Erica (8 de octubre de 2020). «Computer Scientists Break Traveling Salesperson Record». Quanta Magazine.

[14] Hutter, Marcus (2002-06-14). «The Fastest and Shortest Algorithm for All Well-Defined Problems». arXiv:cs/0206022.

[15] Gagliolo, Matteo (20 de noviembre de 2007). «Universal search». Scholarpedia (en inglés) 2 (11): 2575. Bibcode:2007SchpJ...2.2575G. ISSN 1941-6016. doi:10.4249/scholarpedia.2575.

[16] Liang, Faming, Yichen Cheng, and Guang Lin (2014). «Simulated stochastic approximation annealing for global optimization with a square-root cooling schedule». Journal of the American Statistical Association 109 (506): 847-863. S2CID 123410795. doi:10.1080/01621459.2013.872993.

[17] Ingber, Lester (1993). «Simulated annealing: Practice versus theory». Mathematical and Computer Modelling 18 (11): 29-57. doi:10.1016/0895-7177(93)90204-C.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]

[15]

[16]

[17]