3SUM und APSP erstmals wirklich subquadratisch gelöst
Subquadratic 3SUM and Subcubic APSP
Ein neuer Algorithmus für dünne Matrixprodukte widerlegt die 3SUM- und APSP-Hypothesen: 3SUM auf n ganzen Zahlen in O(n^1,9992) und APSP auf gerichteten Graphen mit polynomial beschränkten Gewichten in O(n^2,9995). Die Ergebnisse widerlegen zudem die Exact-Triangle-Hypothese, die Zero-Weight-k-Clique-Hypothesen und drei rechteckige Online-Matrix-Vektor-Vermutungen. Der Schlüssel liegt in einer Modifikation von Coppersmiths rechteckiger Matrixmultiplikation, die nur die benötigten Einträge berechnet.
Wir geben die ersten polynomialen Verbesserungen gegenüber den Lehrbuchalgorithmen für 3SUM und All-Pairs Shortest Paths (APSP): Wir zeigen, wie man 3SUM auf n ganzen Zahlen polynomialer Größe deterministisch in O(n^1,9992) Zeit löst und APSP auf gerichteten Graphen mit n Knoten und polynomial beschränkten ganzzahligen Gewichten in O(n^2,9995) Zeit. Dies widerlegt die 3SUM- und APSP-Hypothesen.