CAE UNA BARRERA DE 1962 EN INFORMÁTICA

Un ciclo hamiltoniano es un viaje de ida y vuelta por una red que visita cada punto exactamente una vez y regresa al inicio. En una red dirigida, cada enlace es una flecha que solo puede recorrerse en un sentido, como una calle de sentido único. La versión ponderada de este problema es el problema del viajante asimétrico.

Decidir si existe un ciclo así es un problema difícil de manual. En 1962, Richard Bellman y, de forma independiente, Michael Held y Richard Karp propusieron algoritmos de programación dinámica que lo resuelven en un tiempo de aproximadamente 2ⁿ para una red de n puntos (salvo factores que solo crecen de forma polinómica). Durante más de sesenta años, nadie logró hacerlo fundamentalmente mejor en redes dirigidas generales.

El primo no dirigido ya había caído

Para redes con enlaces de doble sentido, Andreas Björklund rompió la barrera en 2014 con un algoritmo aleatorizado que se ejecuta en 1,657ⁿ, un trabajo que le valió el Premio Nerode EATCS–IPEC de 2016, según el artículo. Sigue siendo el más rápido conocido para redes no dirigidas generales. En las dirigidas, solo hubo avances en casos particulares —redes bipartitas, redes con pocos enlaces por punto— o bajo una hipótesis no demostrada, la conjetura del rango asintótico de Strassen.

La nueva cota

Tomohiro Koana, de la Universidad de Tokio, y Soh Kumabe, de la empresa tokiota CyberAgent, presentan ahora un algoritmo aleatorizado que decide el problema dirigido en un tiempo

O((375/196)ⁿ) = O(1,9133ⁿ)**.

Para redes dirigidas generales, es la primera mejora de la base de la exponencial desde 1962.

Contar en pares e impares

La dificultad es sutil. Contar los ciclos módulo 2 —saber solo si su número es par o impar— ya era posible por debajo de 2ⁿ. Pero un número par de ciclos distinto de cero tiene exactamente el mismo aspecto que cero. La solución clásica consiste en dar a los enlaces pesos aleatorios para que, para algún peso total, una solución se vuelva única (el lema de aislamiento); pero el método rápido de recuento de paridad no podía manejar pesos.

La receta de los autores, en palabras sencillas:

1. Adivinar una flecha del ciclo y buscar, en su lugar, un camino que pase por todos los puntos desde un extremo de esa flecha hasta el otro.
2. Borrar cada flecha al azar con probabilidad 1/50.
3. En cada punto, crear tres grupos de flechas entrantes y copiar cada flecha superviviente en un conjunto aleatorio no vacío de grupos.
4. Si existe un recorrido, entonces con probabilidad al menos (49/50)ⁿ⁻¹ se puede elegir un grupo por punto de modo que el número de caminos válidos sea impar.
5. Dar a cada grupo —no a cada flecha— un peso aleatorio. Ahora el truco del aislamiento funciona, y bastan unas (50/49)ⁿ repeticiones.
6. Cada repetición calcula los recuentos de paridad para cada peso total en un tiempo (15/8)ⁿ, mediante sumas de determinantes de matrices debidas a Björklund, Kaski y Koutis y una «linealización» aleatoria que también usaron Arvind y Guruswami.

Al multiplicar ambos factores: (50/49)ⁿ × (15/8)ⁿ = (375/196)ⁿ ≈ 1,9133ⁿ.

Una demostración generada por una máquina

El artículo termina con una declaración sobre IA generativa: ChatGPT 6 Astra generó la demostración del teorema principal y ayudó a redactar el manuscrito. Los autores aportaron los enunciados de las proposiciones intermedias, que ofrecen una lectura combinatoria de la solución original del modelo; después lo verificaron y revisaron todo, y asumen plena responsabilidad.

El resultado es teórico —no se ejecutó ningún programa— y el algoritmo es aleatorizado, con una pequeña probabilidad de error en un sentido u otro. Entre 1,9133 para las calles de sentido único y 1,657 para las de doble sentido, sigue abierta una amplia brecha.