Un algoritmo rompe el límite cuadrático de 3SUM y APSP
Subquadratic 3SUM and Subcubic APSP
Un nuevo artículo presenta el primer algoritmo que resuelve 3SUM en tiempo O(n^1.9992) y APSP en O(n^2.9995), refutando así las conjeturas de 3SUM y APSP. El avance se basa en un algoritmo para productos de matrices delgadas que modifica una variante del método de Coppersmith. Esto también refuta otras conjeturas relacionadas y acelera diversos problemas.
Esto refuta las conjeturas de 3SUM y APSP. Usando reducciones conocidas, también refutamos las versiones de valores reales de las conjeturas de 3SUM y APSP, la conjetura del Triángulo Exacto, las conjeturas de k-Clique de Peso Cero, y las tres conjeturas rectangulares con pistas de Online Matrix--Vector de van den Brand, Nanongkai y Saranurak, y damos aceleraciones polinómicas para una variedad de otros problemas.