La imprevisibilidad puede ayudar a los informáticos a resolver problemas que de otro modo serían intratables.

Un artículo de Ben Brubaker. Historia original reimpresa con permiso de Quanta Magazine, una publicación editorialmente independiente respaldada por la Fundación Simons.

Desde los primeros días de la informática, un campo conocido por su enfoque metódico para la resolución de problemas, la aleatoriedad ha jugado un papel importante. El primer programa que se ejecutó en el primer ordenador electrónico de uso general del mundo utilizó la aleatoriedad para simular procesos nucleares. Desde entonces se han utilizado enfoques similares en astrofísica, climatología y economía. En todos estos casos, introducir números aleatorios en ciertos pasos del algoritmo ayuda a los investigadores a tener en cuenta la incertidumbre sobre las muchas formas en que pueden desarrollarse los procesos complejos.

Pero agregar aleatoriedad en un algoritmo también puede ayudarlo a calcular la respuesta correcta a preguntas inequívocas de verdadero o falso. «Simplemente dices ‘Está bien, déjame rendirme, déjame no intentarlo, déjame elegir algo al azar'», explica Eric Blais, científico informático de la Universidad de Waterloo. “Para un montón de problemas, este termina siendo un enfoque ganador”.

Supongamos que quieres determinar si un número dado es primo (divisible solo por 1 y por sí mismo) o compuesto (también divisible por otros números enteros). Simplemente podrías intentar dividirlo entre todos los factores posibles, pero para números grandes este método de «fuerza bruta» y otros algoritmos de factorización son terriblemente lentos. Y si el número resulta ser compuesto, los algoritmos de factorización te dicen los valores de sus divisores, más información de la que pediste. Si solo te importa la «primalidad» de un número, ¿existe un algoritmo más eficiente?

Lo hay si usas la aleatoriedad. La idea básica se remonta a un resultado del matemático francés del siglo XVII Pierre de Fermat, conocido como su “pequeño teorema”. Fermat consideró dos números enteros, llámelos N y x. Demostró que si N es un número primo, entonces x^N – x es siempre un múltiplo de N, independientemente del valor de x. De manera equivalente, si x^N – x no es un múltiplo de N, entonces N no puede ser un número primo. Pero la afirmación inversa no siempre es cierta: si x^N – x es un múltiplo de N, entonces N suele ser primo, aunque no siempre.

Para convertir el pequeño teorema de Fermat en una prueba de primalidad, simplemente toma el N que te interesa, elige x al azar y reemplaza los dos números en x^N – x. Si el resultado no es un múltiplo de N, entonces ya está: sabes que N es definitivamente compuesto. Si el resultado es un múltiplo de N, probablemente N sea primo. Ahora elige otra x aleatoria e inténtalo de nuevo. En la mayoría de los casos, después de algunas docenas de intentos, puedes concluir con casi certeza que N es un número primo. “Haces esto una pequeña cantidad de veces”, explica Blais, “y de alguna manera ahora tu probabilidad de tener un error es menor que la probabilidad de que un asteroide golpee la Tierra entre ahora y cuando mires la respuesta”.

Las primeras pruebas de primalidad utilizando algoritmos aleatorios (basados en refinamientos del pequeño teorema de Fermat) marcaron el comienzo de una nueva era. Problema tras problema resultó ser mucho más fácil de resolver con aleatoriedad que con algoritmos no aleatorios o deterministas. La clave era reformular cada problema como uno que pudiera resolverse rápidamente dado un valor apropiado para algún número x, y luego probar que casi cualquier x valdría. La solución funciona a pesar de que los investigadores no tienen idea de cómo determinar si una opción específica es buena. Los matemáticos han bromeado diciendo que este desafío inusual es similar a encontrar paja en un pajar.

Pero estos éxitos hicieron que los investigadores se preguntaran por qué la aleatoriedad debería ayudar con problemas como las pruebas de primalidad, que consisten todos en encontrar patrones ocultos no aleatorios. “Hay algo un poco paradójico al respecto”, afirma Rahul Santhanam, científico informático de la Universidad de Oxford. “La aleatoriedad pura te ayuda a encontrale el truco a la estructura que resuelve el problema”.

En 1994, los informáticos Noam Nisan y Avi Wigderson ayudaron a resolver esta confusión al demostrar que la aleatoriedad, aunque útil, probablemente no sea necesaria. Demostraron que una de dos cosas debe ser cierta: o todos los problemas que se pueden resolver de manera eficiente usando la aleatoriedad también tienen algoritmos deterministas rápidos, o muchos problemas con fama de difíciles son secretamente fáciles. Los informáticos consideran muy improbable la segunda posibilidad.

De hecho, a los científicos informáticos a menudo les resulta más fácil desarrollar un algoritmo determinista comenzando con una versión aleatoria y luego «desaleatoriazarla». “Una vez que la tengo, de repente veo una forma muy obvia de hacerla determinista”, afirma Eli Upfal, científico informático de la Universidad de Brown. “Pero si no hubiese pensado en ella de forma aleatoria como una pregunta probabilística, probablemente no se me habría ocurrido”.

Casi 30 años después de la prueba histórica de Nisan y Wigderson, los algoritmos aleatorios siguen siendo tan populares como siempre, porque la desaleatorización puede ser complicada y los algoritmos deterministas a menudo son eficientes solo en principio. No fue hasta 2002 que tres investigadores encontraron una forma de eliminar la aleatoriedad de las pruebas de primalidad y, en la práctica, su algoritmo es mucho más lento que los mejores algoritmos aleatorios. Para otros problemas es difícil incluso saber por dónde empezar: el algoritmo más conocido tiene un problema del huevo y la gallina del que solo se puede escapar a través de la aleatoriedad.

Ese es el caso de un avance reciente en la teoría de grafos. El año pasado, tres científicos informáticos desarrollaron un algoritmo rápido para encontrar la ruta más corta a través de un grafo, una red de nodos conectados por segmentos lineales, que funciona incluso cuando algunos segmentos se restan de la longitud total de la ruta en lugar de sumarse. Su algoritmo implicaba transformar el grafo en uno más simple eliminando ciertos segmentos, resolver el problema del grafo simplificado y luego tener en cuenta los segmentos eliminados. Pudieron demostrar que el algoritmo se ejecutaría rápidamente si ninguna ruta más corta pasa a través de demasiados segmentos eliminados; de lo contrario, el último paso emplearía demasiado tiempo.

Pero, ¿cómo decidir qué segmentos eliminar en primer lugar? No solo es difícil encontrar el conjunto ideal de segmentos de forma determinista, es imposible. El conjunto depende de qué caminos sean los más cortos, el mismo problema que los tres investigadores estaban tratando de resolver. Pero aunque no pudieron encontrar el mejor conjunto de segmentos para eliminar, pudieron demostrar que la mayoría de las elecciones aleatorias serían lo bastante buenas, y eso fue suficiente para romper el ciclo autorreferencial. En los raros casos en los que el algoritmo toma una decisión desafortunada y se atasca en el último paso, solo hay que pararlo y ejecutarlo nuevamente.

“La aleatoriedad es básicamente una forma de garantizar que algo es cierto sobre la solución óptima sin conocer la solución óptima”, explica Aaron Bernstein, uno de los autores del nuevo algoritmo.

La aleatoriedad ha encontrado innumerables otros usos en la informática, desde la criptografía hasta la teoría de juegos y el aprendizaje automático. Lo más probable es que esté aquí para quedarse.

El artículo original, How Randomness Improves Algorithms, se publicó el 3 de abril de 2023 en Quanta Magazine.

Traducido por César Tomé López