Un algoritmo galáctico es aquel que supera a cualquier otro algoritmo para problemas que son suficientemente grandes, pero donde "suficientemente grande" es tan grande que el algoritmo nunca se utiliza en la práctica. Los algoritmos galácticos fueron nombrados así por Richard Lipton y Ken Regan, [1] ya que nunca se utilizarán en ninguno de los conjuntos de datos meramente terrestres que encontramos aquí en la Tierra.
Un ejemplo de un algoritmo galáctico es la forma más rápida conocida de multiplicar dos números, [2] que se basa en una transformada de Fourier de 1729 dimensiones . [3] Esto significa que no alcanzará su eficiencia declarada hasta que los números tengan al menos 2 1729 12 bits (al menos 10 10 38 dígitos), que es mucho más grande que el número de átomos en el universo conocido. Entonces este algoritmo nunca se usa en la práctica. [4]
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 eventualmente pueden usarse para crear algoritmos prácticos.
- Los tamaños de las computadoras pueden alcanzar el punto de cruce, por lo que un algoritmo previamente impráctico se vuelve práctico.
- 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, hacer avanzar la teoría de los algoritmos. Como dice Lipton: [1]
Del mismo modo, un El algoritmo para el problema de satisfacibilidad booleano , aunque inutilizable en la práctica, resolvería el problema P versus NP , el problema abierto más importante en ciencias de la computación y uno de los Problemas del Premio Millennium . [5]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 existe 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 utilice, pero sin duda dará forma a la investigación futura sobre factorización.
Ejemplos de
Hay varios algoritmos bien conocidos con un comportamiento asintótico que supera al mundo, pero solo en problemas impracticablemente grandes:
- Multiplicación de matrices: la primera mejora con respecto a 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 utiliza en la práctica. Otras extensiones de esto, utilizando una sofisticada teoría de grupos, son el algoritmo Coppersmith-Winograd y sus sucesores ligeramente mejores, que entregan O ( N 2.373 ). Estos 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 mostró un código simple pero poco práctico que podía alcanzar la capacidad de un canal . Requiere asignar una palabra de código aleatoria a cada mensaje de N bits posible, luego decodificar encontrando la palabra de código más cercana. Si N se elige lo suficientemente grande, esto supera a cualquier código existente y puede acercarse arbitrariamente a la capacidad del canal. Desafortunadamente, cualquier N lo suficientemente grande como para superar los códigos existentes también es completamente impráctico. [7] Estos códigos, aunque nunca se utilizaron, inspiraron décadas de investigación en algoritmos más prácticos que hoy pueden alcanzar tasas arbitrariamente cercanas a la capacidad del canal. [8]
- El problema de decidir si una gráfica G contiene a H como menor es NP-completo en general, pero donde H es fijo, se puede resolver en tiempo polinómico. El tiempo de funcionamiento para comprobar si H es menor de edad de G en este caso es O ( n 2 ), [9] , donde n es el número de vértices en G y los grandes O notación cueros una constante que depende superexponentially en H . La constante es mayor que(usando la notación de flecha hacia arriba de Knuth ), donde h es el número de vértices en H . [10]
- Para los criptógrafos, una "ruptura" criptográfica es algo más rápido que un ataque de fuerza bruta, es decir, realizar un descifrado 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 AES de 128 bits , que requiere solo 2 126 operaciones. [11] A pesar de ser poco práctico, las rupturas teóricas 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 de comercio en un espacio métrico fue el muy simple algoritmo de Christofides que produjo una trayectoria como máximo un 50% más larga que la óptima. (Muchos otros algoritmos normalmente podrían funcionar mucho mejor, pero no se pudo demostrar que lo hicieran). 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á nunca a este algoritmo por su mínima mejora, todavía se considera importante porque "esta minúscula mejora rompe tanto un atolladero teórico como uno psicológico". [13]
- Existe un algoritmo único conocido como "búsqueda de Hutter" que puede resolver cualquier problema bien definido en un tiempo asintóticamente óptimo, salvo algunas salvedades. Sin embargo, sus constantes ocultas en el tiempo de ejecución son tan grandes que nunca sería práctico para nada. [14] [15]
Referencias
- ↑ a b Lipton, Richard J. y Kenneth W. Regan (2013). "David Johnson: algoritmos galácticos" . Personas, problemas y pruebas . Heidelberg: Springer Berlín. págs. 109–112.CS1 maint: varios nombres: lista de autores ( enlace )
- ^ David, Harvey; Hoeven, Joris van der (marzo de 2019). "Multiplicación de enteros en el tiempo O (n log n)" . HAL . hal-02070778.
- ^ David Harvey (abril de 2019). "Hemos encontrado una forma más rápida de multiplicar números realmente grandes" . Phys.org.
- ^ "Hemos encontrado una forma más rápida de multiplicar números realmente grandes" . 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 escribió en un átomo de hidrógeno, hay no habría suficiente espacio disponible en el universo observable para escribirlos ".
- ^ Fortnow, L. (2009). "El estado del problema P versus NP" (PDF) . Comunicaciones de la ACM . 52 (9): 78–86. doi : 10.1145 / 1562164.1562186 .
- ^ Le Gall, F. (2012), "Algoritmos más rápidos para la multiplicación de matrices rectangulares", Actas del 53 ° Simposio anual del IEEE sobre fundamentos de la informática (FOCS 2012) , págs. 514–523, arXiv : 1204.1111 , doi : 10.1109 / FOCS .2012.80
- ^ Larry Hardesty (19 de enero de 2010). "Explicado: El límite de Shannon" . Oficina de noticias del MIT.
- ^ "Códigos de aproximación a la capacidad" (PDF) .
- ^ Kawarabayashi, KI; Kobayashi, Y .; Reed, B. (2012). "El problema de los caminos disjuntos en el tiempo cuadrático" . Revista de Teoría Combinatoria, Serie B . 102 (2): 424–435. doi : 10.1016 / j.jctb.2011.07.004 .
- ^ Johnson, David S. (1987). "La columna NP-completitud: una guía continua (edición 19)". Revista de algoritmos . 8 (2): 285-303. CiteSeerX 10.1.1.114.3864 . doi : 10.1016 / 0196-6774 (87) 90043-5 .
- ^ Biaoshuai Tao y Hongjun Wu (2015). Seguridad y privacidad de la información . Apuntes de conferencias en Ciencias de la Computación. 9144 . págs. 39–56. doi : 10.1007 / 978-3-319-19962-7_3 . ISBN 978-3-319-19961-0.
- ^ 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 ].
- ^ Erica Klarreich (8 de octubre de 2020). "Los informáticos rompen el récord de vendedor ambulante" .
- ^ 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 .
- ^ Gagliolo, Matteo (20 de noviembre de 2007). "Búsqueda universal" . Scholarpedia . 2 (11): 2575. Bibcode : 2007SchpJ ... 2.2575G . doi : 10.4249 / scholarpedia.2575 . ISSN 1941-6016 .