Damos as primeiras melhorias polinomiais sobre os algoritmos clássicos para 3SUM e Caminhos Mais Curtos entre Todos os Pares (APSP): mostramos como resolver deterministicamente 3SUM em n inteiros de tamanho polinomial em tempo O(n^{1.9992}) e APSP em grafos direcionados com n vértices e pesos inteiros polinomialmente limitados em tempo O(n^{2.9995}). Isso refuta as hipóteses de 3SUM e APSP. Usando reduções conhecidas, também refutamos as versões de valor real das hipóteses de 3SUM e APSP, a hipótese do Triângulo Exato, as hipóteses de k-Clique de Peso Zero, e as três conjecturas retangulares de Matriz-Vetor Online de van den Brand, Nanongkai e Saranurak, e damos acelerações polinomiais para uma variedade de outros problemas.
Todos esses resultados seguem de um único novo algoritmo para produtos de matrizes finas. Seja X uma matriz inteira N×D e Y uma matriz inteira D×N com D ≤ N^{1/18}, e seja W qualquer conjunto de no máximo N^2/√D posições. Calculamos as entradas (XY)[I, J], (I, J)∈W, em O(N^2/D^{0.063}) operações, o que é polinomialmente menos que o tempo necessário para escrever XY ou para calcular N^2/√D produtos internos um a um.
Projetamos este algoritmo modificando uma variante do algoritmo de multiplicação de matrizes retangulares de Coppersmith, construído a partir de uma identidade de dez multiplicações de Schönhage, para realizar apenas as operações necessárias para as entradas em W, e mostramos que poucas operações são necessárias. Interpretado como um algoritmo de grafo, isso resolve o problema do Triângulo Esparso de Todas as Arestas em tempo verdadeiramente subquadrático em grafos tripartidos esparsos e desequilibrados onde duas partes têm n vértices, mas uma parte tem n^{ε} vértices para ε<0.12. Por reduções conhecidas, o Triângulo Exato, e portanto 3SUM e APSP, reduzem-se a este problema.
Também fornecemos uma versão de estrutura de dados que responde a consultas para entradas individuais de XY, não conhecidas antecipadamente. Histórico de submissão: De Josh Alman [ver e-mail] [v1]Seg, 5 Out 2026 17:44:29 UTC (93 KB).
Fonte: Hacker News · Resumido por HeadlinesBriefing