Algoritmo galáctico

Un ejemplo de algoritmo galáctico es la forma más rápida conocida de multiplicar dos números , ^{[ 4 ]} que se basa en una transformada de Fourier de 1729 dimensiones . ^{[ 5 ]} Necesita${\displaystyle O(n\log n)}$operaciones de bits, pero como las constantes ocultas por la notación O grande son grandes, nunca se utiliza 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 refinamientos adicionales, el algoritmo pueda volverse práctico para números con apenas miles de millones o billones de dígitos". ^{[ 5 ]}

La prueba de primalidad AKS es galáctica. Es el algoritmo conocido con la base teórica más sólida que puede tomar un número arbitrario y determinar si es primo . En particular, se demuestra que es de tiempo polinomial , determinista e incondicionalmente correcto . Todos los demás algoritmos conocidos no cumplen al menos uno de estos criterios, pero las deficiencias son menores y los cálculos son mucho más rápidos, por lo que se utilizan en su lugar. En la práctica, ECPP es mucho más rápido que AKS, pero nunca se ha demostrado que sea de tiempo polinomial. La prueba de Miller-Rabin también es mucho más rápida que AKS, pero solo produce un resultado probabilístico. Sin embargo, la probabilidad de error se puede reducir a valores arbitrariamente pequeños (por ejemplo,${\displaystyle <10^{-100}}$), suficientemente bueno para fines prácticos. También existe una versión determinista de la prueba de Miller-Rabin, que se ejecuta en tiempo polinomial sobre todas las entradas, pero su corrección depende de la hipótesis generalizada de Riemann (que es ampliamente aceptada, pero no probada). La existencia de estas alternativas (mucho) más rápidas hace que AKS no se utilice en la práctica.

La primera mejora sobre la multiplicación de matrices por fuerza bruta (que toma${\displaystyle O(n^{3})}$operaciones) fue el algoritmo de Strassen : un algoritmo recursivo que toma${\displaystyle O(n^{2.807})}$operaciones. Este algoritmo no es galáctico y se utiliza en la práctica. Otras extensiones de este, que utilizan teoría de grupos sofisticada , son el algoritmo de Coppersmith-Winograd y sus sucesores ligeramente mejores, que toman${\displaystyle O(n^{2.373})}$operaciones. Estas son galácticas: "Sin embargo, destacamos 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 sean poco prácticos." ^{[ 6 ]}

Claude Shannon demostró 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 clave aleatoria a cada posible${\displaystyle n}$Mensaje de -bits, luego decodificación mediante la búsqueda de la palabra clave más cercana. Si${\displaystyle n}$Si se elige un tamaño suficientemente grande, esto supera cualquier código existente y puede acercarse arbitrariamente a la capacidad del canal. Desafortunadamente, cualquier${\displaystyle n}$Lo suficientemente grande como para superar los códigos existentes también es completamente impracticable. ^{[ 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 un gráfico${\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 menor de edad${\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 de flecha hacia arriba de Knuth , donde${\displaystyle h}$es el número de vértices en${\displaystyle H}$. ^{[ 10 ]} Incluso el caso de${\displaystyle h=4}$no se puede calcular razonablemente ya que la constante es mayor que 2 pentado por 4, o 2 tetrado por 65536, es decir,${\displaystyle 2\uparrow \uparrow \uparrow 4={}^{65536}2=\underbrace {2^{2^{\cdot ^{\cdot ^{2}}}}} _{65536}}$.

En la jerga criptográfica , una "ruptura" es cualquier ataque más rápido en expectativa que la fuerza bruta , es decir, realizar un descifrado de prueba para cada clave posible. Para muchos sistemas criptográficos, se conocen rupturas, pero siguen siendo prácticamente inviables con la tecnología actual. Un ejemplo es el mejor ataque conocido contra AES de 128 bits , que requiere solo${\displaystyle 2^{126}}$operaciones. ^{[ 11 ]} A pesar de ser poco prácticos, los análisis teóricos pueden brindar información sobre patrones de vulnerabilidad y, a veces, conducir al descubrimiento de vulnerabilidades explotables.

Durante varias décadas, la mejor aproximación conocida al problema del viajante en un espacio métrico fue el muy simple algoritmo de Christofides , que producía una ruta como máximo un 50% más larga que la óptima. (Muchos otros algoritmos solían hacerlo mucho mejor, pero no se podía demostrar que lo hicieran). En 2020, se descubrió un algoritmo más nuevo y mucho más complejo que puede superarlo por${\displaystyle 10^{-34}}$por ciento. ^{[ 12 ]} Aunque nadie cambiará jamás a este algoritmo por su mínima mejora en el peor de los casos, todavía se considera importante porque "esta minúscula mejora rompe un estancamiento tanto teórico como psicológico". ^{[ 13 ]}

Un único algoritmo, la "búsqueda de Hutter", puede resolver cualquier problema bien definido en un tiempo asintóticamente óptimo, salvo algunas excepciones . 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 prueba), buscando una prueba de corrección para cada algoritmo. Dado que la prueba de corrección es de tamaño finito, "solo" añade una constante y no afecta al tiempo de ejecución asintótico. Sin embargo, esta constante es tan grande que el algoritmo es completamente impráctico. ^{[ 14 ] [ 15 ]} Por ejemplo, si la prueba de corrección más corta de un algoritmo dado es de 1000 bits de longitud, la búsqueda examinará primero al menos otras 2 ⁹⁹⁹ pruebas potenciales.

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 (implementadas por programas) que describen perfectamente las observaciones previas se utilizan para calcular la probabilidad de la siguiente observación, otorgando mayor peso a las teorías computables más cortas. Nuevamente, la búsqueda sobre todas las explicaciones posibles hace que este procedimiento sea de gran alcance.

Se ha demostrado que el recocido simulado , cuando se utiliza con un esquema de enfriamiento logarítmico, encuentra el óptimo global de cualquier problema de optimización. ^{[ 16 ]} Sin embargo, dicho esquema de enfriamiento resulta en tiempos de ejecución totalmente imprácticos y nunca se utiliza. ^{[ 17 ]} No obstante, el conocimiento de la existencia de este algoritmo ideal ha dado lugar a variantes prácticas capaces de encontrar soluciones muy buenas (aunque no demostrablemente óptimas) a problemas de optimización complejos. ^{[ 18 ] [ 19 ]}

El algoritmo MST de tiempo lineal esperado es capaz de descubrir el árbol de expansión mínima de un grafo en${\displaystyle O(m+n)}$, dónde${\displaystyle m}$es el número de aristas y${\displaystyle n}$es el número de nodos del grafo. ^{[ 20 ]} Sin embargo, el factor constante que se oculta con la notación Big O es lo suficientemente grande como para hacer que el algoritmo sea impracticable. Existe una implementación disponible públicamente ^{[ 21 ]} y, dadas las constantes de implementación estimadas experimentalmente, solo sería más rápido que el algoritmo de Borůvka para grafos en los que${\displaystyle m+n>9\cdot 10^{151}}$. ^{[ 22 ]}

Los investigadores han encontrado un algoritmo que logra el mejor rendimiento asintótico posible ^{[ 23 ]} en términos de compensación tiempo-espacio en tablas hash . ^{[ 24 ]} Pero sigue siendo puramente teórico: "A pesar de la eficiencia sin precedentes de la nueva tabla hash, es poco probable que alguien intente construirla pronto. Es demasiado complicado de construir" ^{[ 25 ]} y "en la práctica, las constantes realmente importan. En el mundo real, un factor de 10 es determinante". ^{[ 25 ]}

La conectividad en grafos no dirigidos (también conocida como USTCON, por Undirected Source-Target CONnectivity) es el problema de decidir si existe un camino entre dos nodos en un grafo no dirigido, o en otras palabras, si están en el mismo componente conectado . Cuando el uso de${\displaystyle O({\text{N}})}$Si el espacio lo permite, las soluciones de tiempo polinomial, como el algoritmo de Dijkstra, se conocen y se utilizan desde hace décadas. Pero durante muchos años se desconocía si esto podía hacerse de forma determinista en${\displaystyle O({\text{log N}})}$espacio (clase L ), aunque se sabía que era posible con algoritmos aleatorios (clase RL ).

Un artículo revolucionario de 2008 de Omer Reingold demostró que USTCON está de hecho en L , ^{[ 26 ]} proporcionando un algoritmo con un requisito de espacio asintóticamente mejor. Sin embargo, la constante muy grande del algoritmo está oculta por el${\displaystyle O({\text{log N}})}$significa que en cualquier problema realista consume significativamente más memoria y tiempo de cálculo que el bien conocido${\displaystyle O({\text{N}})}$algoritmos. A pesar de no utilizarse en la práctica, el artículo sigue siendo un hito en la teoría y ha sido citado más de 1000 veces hasta 2026.

Los códigos de verificación de paridad de baja densidad , también conocidos como códigos LDPC o códigos Gallager, son un ejemplo de un algoritmo que era galáctico cuando se desarrolló por primera vez, pero que se volvió práctico a medida que mejoró la computación. Fueron concebidos originalmente por Robert G. Gallager en su tesis doctoral ^{[ 27 ]} en el Instituto Tecnológico de Massachusetts en 1960. ^{[ 28 ] [ 29 ]} Aunque su rendimiento era mucho mejor que el de otros códigos de la época, alcanzando el límite de Gilbert-Varshamov para códigos lineales , los códigos fueron ignorados en gran medida porque su algoritmo de decodificación iterativa era prohibitivamente costoso computacionalmente para el hardware disponible. ^{[ 30 ]}

El interés por los códigos LDPC resurgió tras la invención de los códigos turbo (1993), estrechamente relacionados, cuyo algoritmo de decodificación iterativo similar superaba a otros códigos utilizados en aquel entonces. Los códigos LDPC fueron redescubiertos posteriormente en 1996 ^{[ 31 ]} y se popularizaron como una alternativa libre de patentes ^{[ 32 ]} . Si bien las patentes de los códigos turbo ya han expirado, los códigos LDPC también presentan algunas ventajas técnicas y se utilizan en numerosas aplicaciones en la actualidad.

La triangulación de polígonos consiste en la división de un polígono en triángulos que no se superponen. Bernard Chazelle demostró en 1991 que cualquier polígono simple puede triangularse en tiempo lineal. ^{[ 33 ]} Sin embargo, el algoritmo propuesto es extremadamente complejo, y existen algoritmos mucho más simples ^{[ 34 ]} con un tiempo casi lineal.${\displaystyle O({\text{Nlog}}^{*}{\text{N}})}$El rendimiento está disponible, por lo que se utilizan en su lugar. ^{[ 35 ]} "Su [el trabajo de Chazelle] representa un importante avance teórico. Sin embargo, su algoritmo O(n) ha resultado muy difícil de programar y, por lo tanto, según el conocimiento de los autores, todavía no hay una implementación práctica disponible." ^{[ 36 ]}