💻 ciencias de la computación

Truly Subquadratic 3SUM and Truly Subcubic APSP via Triangles in Sparse Lopsided Graphs

Este artículo presenta las primeras mejoras polinómicas sobre los algoritmos de libro de texto para 3SUM y All-Pairs Shortest Paths (APSP) mediante la introducción de un nuevo algoritmo para computar entradas dispersas de productos de matrices en grafos desequilibrados, lo cual refuta las hipótesis de 3SUM y APSP y produce aceleraciones para numerosos problemas relacionados.

Autores originales: Josh Alman, Virginia Vassilevska Williams

Publicado 2026-10-06

📖 5 min de lectura🧠 Análisis profundo

CC BY 4.0

Autores originales: Josh Alman, Virginia Vassilevska Williams

Artículo original bajo licencia CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ Esta es una explicación generada por IA del artículo a continuación. No ha sido escrita ni avalada por los autores. Para mayor precisión técnica, consulte el artículo original. Leer descargo de responsabilidad completo

En el vasto paisaje de la informática, existen problemas que han resistido obstinadamente cualquier mejora durante décadas, actuando como reductores de velocidad para nuestra capacidad de procesar información más rápido. Dos de los más famosos de estos son el problema de la "suma de tres" (three-sum) y el problema de los "caminos más cortos entre todos los pares" (all-pairs shortest paths). El primero plantea una pregunta sencilla: dada una lista de números, ¿puedes encontrar tres que sumen cero? Durante mucho tiempo, la mejor forma de resolver esto para una lista grande de números tomaba un tiempo que crecía con el cuadrado del tamaño de la lista. El segundo problema pide la distancia más corta entre cada par de ciudades en una red de carreteras. El mejor método conocido para esto siempre ha tomado un tiempo que crece con el cubo del número de ciudades. Durante años, los informáticos creyeron que estos límites eran inquebrantables, formando un conjunto de reglas llamadas "hipótesis" que sugerían que ningún algoritmo podría ser jamás significativamente más rápido que estos métodos de los libros de texto. Estos problemas no son solo acertijos abstractos; sustentan todo, desde el software de mapas hasta la detección de patrones en datos complejos, por lo que encontrar una forma de romper estos límites de velocidad sería un cambio monumental en nuestra forma de computar.

Un equipo de investigadores de la Universidad de Columbia y el MIT, trabajando con un modelo de inteligencia artificial desarrollado por Anthropic, ha destrozado estas creencias largamente sostenidas. Han descubierto una nueva forma de resolver estos problemas que es genuinamente más rápida que los mejores métodos anteriores. En lugar de tomar un tiempo proporcional al cuadrado del tamaño de la entrada para el problema de la suma de tres, su nuevo método lo resuelve en un tiempo que es ligeramente menor al cuadrado. Del mismo modo, para el problema de los caminos más cortos, han reducido el tiempo requerido a ligeramente menos del cubo del número de ciudades. Esto no es un ajuste menor o un truco que solo funciona en casos especiales; es una mejora fundamental que se aplica a una amplia gama de entradas. Al demostrar que estos problemas pueden resolverse más rápido, los investigadores han refutado efectivamente las hipótesis que afirmaban que no podrían serlo.

El secreto detrás de este avance reside en un nuevo y hábil enfoque para la multiplicación de matrices, que son simplemente cuadrículas de números utilizadas para representar datos. Los investigadores se centraron en un tipo específico de multiplicación de matrices donde las cuadrículas son muy delgadas y largas, en lugar de cuadradas. Se dieron cuenta de que si solo necesitas conocer las respuestas para unos pocos lugares específicos en el resultado final, en lugar de calcular cada uno de los números en toda la cuadrícula, puedes saltarte una cantidad masiva de trabajo. Diseñaron un algoritmo que actúa como un filtro altamente eficiente, ignorando los cálculos que producirían respuestas que nadie pidió. Esta técnica fue construida modificando una identidad matemática antigua, un conjunto de reglas para combinar números, para que funcionara solo en las piezas específicas de información que importaban.

El poder de este descubrimiento proviene de cómo están conectados estos diferentes problemas informáticos. En el mundo de la complejidad fina, los investigadores han pasado años mapeando cómo la resolución de un problema ayuda a resolver otro. Descubrieron que si puedes resolver el problema de la "suma de tres" más rápido, también puedes resolver el problema de los "caminos más cortos" más rápido, y viceversa. El nuevo algoritmo actúa como una llave maestra. Al descifrar el código para este problema específico de multiplicación de matrices, los investigadores desbloquearon soluciones más rápidas para docenas de otros problemas que anteriormente se creían estancados en sus antiguas velocidades. Esto incluye encontrar triángulos en redes, verificar patrones específicos en datos y optimizar varios tipos de tareas de búsqueda y ordenación.

El equipo no solo encontró una posibilidad teórica; proporcionaron un método concreto y determinista que funciona siempre. También demostraron que su enfoque funciona incluso cuando los números involucrados no son solo números enteros sino números reales, que son el tipo de valores utilizados en la mayoría de los cálculos científicos del mundo real. Los investigadores utilizaron una poderosa herramienta de IA para ayudar a verificar sus pruebas matemáticas, asegurando que la lógica detrás de su aceleración fuera sólida. Esta colaboración entre investigadores humanos e inteligencia artificial destaca una nueva era en el descubrimiento científico, donde las máquinas pueden ayudar a descubrir verdades matemáticas profundas que los humanos podrían pasar por alto.

Las implicaciones de este trabajo se extienden mucho más allá de los problemas específicos de la suma de tres y los caminos más cortos. Desafía la idea de que algunos límites computacionales son absolutos. Durante décadas, la comunidad ha aceptado que ciertos problemas requieren una cantidad específica de tiempo para resolverse, y que intentar ir más rápido era fútil. Este trabajo demuestra que esos límites no eran muros, sino meros techos que podían elevarse con la perspectiva adecuada. Aunque los nuevos algoritmos son actualmente demasiado complejos para ser utilizados en el software cotidiano debido a las enormes constantes ocultas en su velocidad, la prueba de que existen cambia la base teórica de la informática. Abre la puerta para que futuros investigadores perfeccionen estos métodos, lo que potencialmente conducirá a herramientas prácticas que puedan procesar conjuntos de datos masivos de manera mucho más eficiente que nunca. Los investigadores han demostrado que incluso los problemas más obstinados pueden ceder ante un pensamiento fresco, probando que las fronteras de lo que es computable siempre valen la pena ser puestas a prueba.

Resumen Técnico: 3SUM verdaderamente subcuadrático y APSP verdaderamente subcúbico mediante Triángulos en Grafos Lopsided Dispersos

1. Planteamiento del Problema

Este artículo aborda dos problemas fundamentales en la teoría de la complejidad de grano fino que han resistido mejoras significativas durante décadas:

3SUM: Dados $n$ enteros de tamaño polinómico, determinar si tres de ellos suman cero. El algoritmo estándar se ejecuta en un tiempo de $O(n^2)$ , y la Hipótesis 3SUM postula que ningún algoritmo puede resolver esto en $O(n^{2-\epsilon})$ para cualquier $\epsilon > 0$ .
All-Pairs Shortest Paths (APSP - Caminos Más Cortos entre Todos los Pares): Dado un grafo dirigido con $n$ vértices y pesos enteros de acotación polinómica, calcular el camino más corto entre todos los pares. Los algoritmos estándar (Floyd-Warshall, Johnson) se ejecutan en $O(n^3)$ tiempo. La Hipótesis APSP postula que ningún algoritmo puede resolver esto en $O(n^{3-\epsilon})$ tiempo.

El artículo también se dirige al problema Exact Triangle (encontrar un triángulo con peso total de aristas igual a cero en un grafo tripartito) y al problema Directed Unweighted APSP (APSP dirigido no ponderado), junto con una amplia variedad de problemas equivalentes a ellos bajo reducciones de grano fino (por ejemplo, producto $(\min, +)$ , Distancia de Edición de Árbol, Zero-Weight $k$ -Clique).

2. Metodología

La contribución central es un nuevo algoritmo para computar un conjunto prescrito de entradas dispersas en el producto de dos matrices "delgadas" (thin).

2.1 Algoritmo de Producto de Matrices Delgadas

Los autores desarrollan un algoritmo determinista para computar un conjunto $W$ de entradas en el producto $XY$ , donde:

$X$ es una matriz entera de $N \times D$ .
$Y$ es una matriz entera de $D \times N$ .
$D \le N^{1/18}$ (las matrices son "delgadas").
$W$ es un conjunto de como máximo $N^2/\sqrt{D}$ posiciones.

Innovación Técnica Clave:
El algoritmo modifica el algoritmo de multiplicación de matrices rectangulares de Coppersmith, el cual se basa a su vez en una identidad de diez multiplicaciones de Schönhage.

Estructura Recursiva: El algoritmo aplica la identidad de Schönhage de forma recursiva. A diferencia de la multiplicación de matrices estándar que computa todas las $N^2$ entradas, este algoritmo poda el árbol de recursión.
Estrategia de Poda: Visita solo las "hojas" del árbol de recursión necesarias para computar las entradas en $W$ .
Codificación Compartida: La fase de "codificación" (combinaciones lineales de bloques de entrada) depende solo de las matrices de entrada, no de las entradas de salida específicas. El algoritmo computa estas codificaciones una sola vez por cada bloque de entrada y las comparte en todos los cálculos requeridos.
Análisis de Hojas: Los autores analizan el "orden" de las hojas en el árbol de recursión. Demuestran que, si bien una sola entrada de salida requiere muchas hojas, la mayoría de las hojas se comparten entre muchas entradas de salida. Al equilibrar cuidadosamente el número de hojas de diferentes órdenes, demuestran que el número total de hojas requeridas para un conjunto disperso $W$ es significativamente menor que el costo de computar el producto completo o computar las entradas individualmente.

Complejidad:
El algoritmo computa las entradas en $W$ en un tiempo de $O(N^2 / D^{0.063})$ (con factores logarítmicos), lo cual es polinómicamente más rápido que el tiempo de $O(N^2)$ requerido para escribir el producto completo o el tiempo de $O(N^2 \sqrt{D})$ requerido para computar las entradas individualmente como productos internos.

2.2 Reducciones a Problemas de Grafos

El algoritmo de matrices se aplica al problema Lopsided All-Edges Sparse Triangle. En este problema, se busca determinar si un conjunto de aristas $(a, b)$ en un grafo tripartito (con partes $A, B$ de tamaño $n$ y una parte media $M$ de tamaño $D \ll n$ ) forman parte de un triángulo.

Interpretación de Matrices: Esto es equivalente a computar las entradas del producto de las matrices de biadyacencia del grafo en las posiciones correspondientes a las aristas en $W$ .
Reducción Determinista: El artículo proporciona una reducción determinista de Exact Triangle (en grafos generales) a Lopsided All-Edges Sparse Triangle. Esto implica el uso de hashing de pesos de aristas módulo un primo elegido determinísticamente para minimizar los falsos positivos, seguido de una búsqueda de testigo.
Cadena de Reducciones: Reducciones de grano fino conocidas vinculan 3SUM y APSP con Exact Triangle. Al componer estas reducciones con el nuevo algoritmo para Lopsided All-Edges Sparse Triangle, los autores derivan algoritmos más rápidos para los problemas originales.

3. Contribuciones Clave y Resultados

3.1 Refutación de Hipótesis

El artículo presenta las primeras mejoras polinómicas sobre los algoritmos de libro de texto para 3SUM y APSP, refutando así las hipótesis de 3SUM y APSP de la complejidad de grano fino.

3SUM: Resuelto determinísticamente en $O(n^{1.9992})$ tiempo para enteros de tamaño polinómico.
APSP: Resuelto determinísticamente en $O(n^{2.9995})$ tiempo para grafos dirigidos con pesos enteros de acotación polinómica.
Exact Triangle: Resuelto determinísticamente en $O(n^{2.9983})$ tiempo.
Directed Unweighted APSP: Resuelto determinísticamente en $O(n^{2+\mu-\epsilon})$ tiempo (donde $\mu < 0.5275$ ), refutando la hipótesis de que el algoritmo de Zwick es óptimo. Esta es la primera mejora que no se deriva únicamente de los límites de la multiplicación de matrices rectangulares más rápidos.

3.2 Variantes de Valores Reales

Utilizando una reducción de Chan, Vassilevska Williams y Xu que se basa únicamente en comparaciones, adiciones y sustracciones, los autores proporcionan algoritmos Las Vegas (aleatorizados con error cero) para las versiones de valores reales de estos problemas:

Real 3SUM: Tiempo esperado de $O(n^{1.998})$ .
Real APSP: Tiempo esperado de $O(n^{2.998})$ .

3.3 Impacto Algorítmico Amplio

A través de reducciones conocidas, la nueva técnica produce aceleraciones polinómicas para una amplia gama de otros problemas, incluyendo:

Producto $(\min, +)$ de matrices.
Distancia de Edición de Árbol (para costos de enteros de acotación polinómica).
Zero-Weight, Min-Weight, y Max-Weight $k$ -Clique para cualquier constante $k \ge 3$ .
Conjeturas de Online Matrix-Vector (OMv): El artículo refuta las variantes "con pistas" (hinted) de la conjetura OMv (específicamente para pistas delgadas) al proporcionar una estructura de datos que preprocesa matrices en tiempo subcuadrático y responde consultas de entrada única en tiempo sublineal respecto a la dimensión interna.
Knapsack y Approximate Subset Sum: Primeros algoritmos verdaderamente subcuadráticos para Unbounded Knapsack y esquemas de aproximación para Subset Sum.

3.4 Versión de Estructura de Datos

Los autores extienden el algoritmo de matrices a una estructura de datos. Tras el preprocesamiento de $X$ e $Y$ en $O(N^2/D^{0.063})$ tiempo, cualquier entrada individual $(XY)[I, J]$ puede computarse en $O(D^{0.437})$ tiempo. Esto permite resolver problemas donde las entradas objetivo no se conocen de antemano.

4. Significado y Reivindicaciones

Los autores consideran este trabajo como un "gran éxito para la complejidad de grano fino".

Reducciones como Algoritmos: El artículo enfatiza que las reducciones de grano fino, utilizadas anteriormente principalmente para inferir dureza condicional, son también algoritmos. Una sola técnica nueva (el algoritmo de producto de matrices delgadas) puede acelerar simultáneamente una vasta red de problemas interconectados.
Refutación del Statu Quo: Los resultados demuestran que los tiempos de ejecución "atascados" para 3SUM y APSP no eran barreras fundamentales, sino artefactos de las técnicas disponibles en ese momento.
Limitaciones y Preguntas Abiertas:
- Los autores señalan que sus técnicas actualmente no mejoran CNF-SAT, Orthogonal Vectors, o $k$ -SUM para $k \ge 4$ , ya que estos problemas no se reducen a las instancias específicas de triángulos dispersos resueltas aquí.
- Los algoritmos son algebraicos y actualmente tienen constantes ocultas grandes, lo que los hace poco prácticos para un uso inmediato en el mundo real.
- El caso balanceado de All-Edges Sparse Triangle (donde las tres partes son de tamaño $n$ ) permanece sin resolver por esta técnica, manteniendo intacta la hipótesis $m^{4/3}$ para ese caso específico.
- El artículo no pretende haber encontrado los exponentes óptimos para estos problemas, señalando que es probable que se logren más mejoras mediante mejores reducciones o identidades algebraicas refinadas.

5. Nota Metodológica sobre el Descubrimiento

El artículo reconoce explícitamente que el algoritmo central fue descubierto por Claude, un modelo de IA desarrollado por Anthropic. Los autores (Josh Alman y Virginia Vassilevska Williams) trabajaron para comprender, simplificar, fortalecer y extender el algoritmo, derivar consecuencias y formalizar los resultados. Los principales resultados fueron verificados utilizando el asistente de pruebas Lean 4. Los autores asumen la responsabilidad total del contenido y la presentación del artículo.