Un equipo de investigadores ha presentado los primeros algoritmos polinómicos que superan a las versiones estándar de los problemas 3SUM y All-Pairs Shortest Paths (APSP). Estos avances, publicados en arXiv, demuestran que es posible resolver 3SUM en tiempo O(n^1.9992) y APSP en O(n^2.9995) para entradas de tamaño polinómico, refutando así las hipótesis computacionales asociadas a estos problemas. La clave de estos resultados es un nuevo algoritmo para productos de matrices delgadas, que permite calcular entradas específicas de una matriz X por Y en tiempo O(N^2/D^0.063), donde D es la dimensión de la matriz. Este método modifica una variante del algoritmo de multiplicación de matrices rectangulares de Coppersmith, optimizada para ejecutar solo las operaciones necesarias para las entradas en un conjunto de posiciones W. Interpretado como un algoritmo de grafos, este enfoque resuelve el problema de triángulos en grafos tripartitos lopsidos y dispersos en tiempo subcuadrático. Además, los autores refutan hipótesis relacionadas con el Exact Triangle, los Zero-Weight k-Clique y varias conjeturas de van den Brand, Nanongkai y Saranurak. Estos hallazgos no solo mejoran la complejidad de 3SUM y APSP, sino que también ofrecen aceleraciones polinómicas para una variedad de otros problemas computacionales, marcando un hito significativo en la teoría de la complejidad.
