💻 ciência da computação

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

Este artigo apresenta as primeiras melhorias polinomiais sobre algoritmos de livro-texto para 3SUM e All-Pairs Shortest Paths (APSP) ao introduzir um novo algoritmo para computar entradas esparsas de produtos de matrizes em grafos desbalanceados, o que refuta as hipóteses de 3SUM e APSP e gera acelerações para inúmeros problemas relacionados.

Autores originais: Josh Alman, Virginia Vassilevska Williams

Publicado 2026-10-06

📖 5 min de leitura🧠 Leitura aprofundada

CC BY 4.0

Autores originais: Josh Alman, Virginia Vassilevska Williams

Artigo original sob licença CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ Esta é uma explicação gerada por IA do artigo abaixo. Não foi escrita nem endossada pelos autores. Para precisão técnica, consulte o artigo original. Ler aviso legal completo

Na vasta paisagem da ciência da computação, existem problemas que resistiram obstinadamente a melhorias por décadas, agindo como lombadas de velocidade em nossa capacidade de processar informações mais rapidamente. Dois dos mais famosos são o problema do "three-sum" (soma de três) e o problema do "all-pairs shortest paths" (caminhos mais curtos entre todos os pares). O primeiro faz uma pergunta simples: dada uma lista de números, você consegue encontrar três que somem zero? Por muito tempo, a melhor maneira de resolver isso para uma lista grande de números levava um tempo que crescia com o quadrado do tamanho da lista. O segundo problema pede a distância mais curta entre cada par de cidades em uma rede de estradas. O melhor método conhecido para isso sempre levou um tempo que cresce com o cubo do número de cidades. Durante anos, cientistas da computação acreditaram que esses limites eram inquebráveis, formando um conjunto de regras chamadas "hipóteses" que sugeriam que nenhum algoritmo poderia jamais ser significativamente mais rápido do que esses métodos de livros didáticos. Esses problemas não são apenas quebra-cabeças abstratos; eles sustentam tudo, desde softwares de mapeamento até a detecção de padrões em dados complexos, de modo que encontrar uma maneira de quebrar esses limites de velocidade seria uma mudança monumental em nossa forma de computar.

Uma equipe de pesquisadores da Universidade de Columbia e do MIT, trabalhando com um modelo de inteligência artificial desenvolvido pela Anthropic, acaba de despedaçar essas crenças mantidas por muito tempo. Eles descobriram uma nova maneira de resolver esses problemas que é genuinamente mais rápida do que os métodos anteriores mais eficientes. Em vez de levar um tempo proporcional ao quadrado do tamanho da entrada para o problema do three-sum, seu novo método o resolve em um tempo ligeiramente menor que o quadrado. Da mesma forma, para o problema dos caminhos mais curtos, eles reduziram o tempo necessário para ligeiramente menos que o cubo do número de cidades. Isso não é um pequeno ajuste ou um truque que só funciona em casos especiais; é uma melhoria fundamental que se aplica a uma ampla gama de entradas. Ao provar que esses problemas podem ser resolvidos mais rapidamente, os pesquisadores refutaram efetivamente as hipóteses que afirmavam que eles não poderiam ser.

O segredo por trás dessa descoberta reside em uma nova e inteligente abordagem para a multiplicação de matrizes, que são simplesmente grades de números usadas para representar dados. Os pesquisadores focaram em um tipo específico de multiplicação de matrizes onde as grades são muito finas e longas, em vez de quadradas. Eles perceberam que, se você só precisa saber as respostas para alguns pontos específicos no resultado final, em vez de calcular cada número individual na grade inteira, você pode pular uma quantidade massiva de trabalho. Eles projetaram um algoritmo que atua como um filtro altamente eficiente, ignorando os cálculos que produziriam respostas para as quais ninguém perguntou. Essa técnica foi construída modificando uma identidade matemática antiga, um conjunto de regras para combinar números, para funcionar apenas nas partes específicas de informação que importavam.

O poder dessa descoberta vem de como esses diferentes problemas de computação estão conectados. No mundo da complexidade fina, pesquisadores passaram anos mapeando como a resolução de um problema ajuda a resolver outro. Eles descobriram que, se você puder resolver o problema do "three-sum" mais rapidamente, também poderá resolver o problema dos "caminhos mais curtos" mais rapidamente, e vice-versa. O novo algoritmo atua como uma chave mestra. Ao decifrar o código para esse problema específico de multiplicação de matrizes, os pesquisadores desbloquearam soluções mais rápidas para dezenas de outros problemas que anteriormente eram considerados presos em suas antigas velocidades. Isso inclui encontrar triângulos em redes, verificar padrões específicos em dados e otimizar vários tipos de tarefas de busca e ordenação.

A equipe não encontrou apenas uma possibilidade teórica; eles forneceram um método concreto e determinístico que funciona sempre. Eles também mostraram que sua abordagem funciona mesmo quando os números envolvidos não são apenas números inteiros, mas números reais, que são os tipos de valores usados na maioria dos cálculos científicos do mundo real. Os pesquisadores usaram uma ferramenta de IA poderosa para ajudar a verificar suas provas matemáticas, garantindo que a lógica por trás de sua aceleração fosse sólida. Essa colaboração entre pesquisadores humanos e inteligência artificial destaca uma nova era na descoberta científica, onde máquinas podem ajudar a descobrir verdades matemáticas profundas que os humanos podem perder.

As implicações deste trabalho estendem-se muito além dos problemas específicos de three-sum e caminhos mais curtos. Elas desafiam a ideia de que alguns limites computacionais são absolutos. Por décadas, a comunidade aceitou que certos problemas exigem uma quantidade específica de tempo para serem resolvidos, e que tentar ser mais rápido era fútil. Este artigo demonstra que esses limites não eram paredes, mas meramente tetos que poderiam ser elevados com a perspectiva certa. Embora os novos algoritmos sejam atualmente muito complexos para serem usados em softwares cotidianos devido às enormes constantes ocultas em sua velocidade, a prova de que eles existem muda a base teórica da ciência da computação. Ela abre as portas para que futuros pesquisadores refinem esses métodos, potencialmente levando a ferramentas práticas que possam processar conjuntos de dados massivos de forma muito mais eficiente do que antes. Os pesquisadores mostraram que mesmo os problemas mais persistentes podem ceder ao pensamento fresco, provando que as fronteiras do que é computável estão sempre valendo a pena serem testadas.

Resumo Técnico: 3SUM Verdadeiramente Subquadrático e APSP Verdadeiramente Subcúbico via Triângulos em Grafos Esparsos Assimétricos

1. Declaração do Problema

Este artigo aborda dois problemas fundamentais na teoria da complexidade de granularidade fina que resistiram a melhorias significativas por décadas:

3SUM: Dados $n$ inteiros de tamanho polinomial, determinar se três somam zero. O algoritmo padrão executa em tempo $O(n^2)$ , e a Hipótese 3SUM postula que nenhum algoritmo pode resolver isso em $O(n^{2-\epsilon})$ para qualquer $\epsilon > 0$ .
Caminhos Curtos de Todos os Pares (APSP): Dado um grafo direcionado com $n$ vértices e pesos inteiros de limite polinomial, calcular o caminho mais curto entre todos os pares. Os algoritmos padrão (Floyd-Warshall, Johnson) executam em $O(n^3)$ tempo. A Hipótese APSP postula que nenhum algoritmo pode resolver isso em $O(n^{3-\epsilon})$ tempo.

O artigo também visa o problema do Triângulo Exato (encontrar um triângulo com peso total de aresta zero em um grafo tripartido) e o problema APSP Não-Ponderado Direcionado, juntamente com uma ampla variedade de problemas equivalentes a eles sob reduções de granularidade fina (ex: produto $(\min, +)$ , Distância de Edição de Árvore, $k$ -Clique de Peso Zero).

2. Metodologia

A contribuição central é um novo algoritmo para computar um conjunto prescrito de entradas no produto de duas matrizes "finas".

2.1 Algoritmo de Produto de Matrizes Finas

Os autores desenvolvem um algoritmo determinístico para computar um conjunto $W$ de entradas no produto $XY$ , onde:

$X$ é uma matriz inteira $N \times D$ .
$Y$ é uma matriz inteira $D \times N$ .
$D \le N^{1/18}$ (as matrizes são "finas").
$W$ é um conjunto de no máximo $N^2/\sqrt{D}$ posições.

Inovação Técnica Principal:
O algoritmo modifica o algoritmo de multiplicação de matrizes retangulares de Coppersmith, que por sua vez é construído sobre uma identidade de dez multiplicações de Schönhage.

Estrutura Recursiva: O algoritmo aplica a identidade de Schönhage recursivamente. Ao contrário da multiplicação de matrizes padrão que computa todas as $N^2$ entradas, este algoritmo poda a árvore de recursão.
Estratégia de Poda: Ele visita apenas as "folhas" da árvore de recursão necessárias para computar as entradas em $W$ .
Compartilhamento de Codificação: A fase de "codificação" (combinações lineares de blocos de entrada) depende apenas das matrizes de entrada, não das entradas específicas de saída. O algoritmo computa essas codificações uma única vez por bloco de entrada e as compartilha em todas as computações necessárias.
Análise de Folhas: Os autores analisam a "ordem" das folhas na árvore de recursão. Eles provam que, embora uma única entrada de saída exija muitas folhas, a maioria das folhas é compartilhada entre muitas entradas de saída. Ao equilibrar cuidadosamente o número de folhas de diferentes ordens, eles mostam que o número total de folhas necessárias para um conjunto esparso $W$ é significativamente menor do que o custo de computar o produto completo ou computar as entradas individualmente.

Complexidade:
O algoritmo computa as entradas em $W$ em $O(N^2 / D^{0.063})$ tempo (com fatores logarítmicos), o que é polinomialmente mais rápido que o tempo $O(N^2)$ necessário para escrever o produto completo ou o tempo $O(N^2 \sqrt{D})$ necessário para computar as entradas individualmente como produtos internos.

2.2 Reduções para Problemas de Grafos

O algoritmo de matriz é aplicado ao problema do Triângulo Esparso de Todas as Arestas Assimétrico (Lopsided All-Edges Sparse Triangle). Neste problema, busca-se determinar se um conjunto de arestas $(a, b)$ em um grafo tripartido (com partes $A, B$ de tamanho $n$ e uma parte central $M$ de tamanho $D \ll n$ ) pertence a um triângulo.

Interpretação Matricial: Isso é equivalente a computar as entradas do produto das matrizes de adjacência bipartida do grafo nas posições correspondentes às arestas em $W$ .
Redução Determinística: O artigo fornece uma redução determinística do Triângulo Exato (em grafos gerais) para o Triângulo Esparso de Todas as Arestas Assimétrico. Isso envolve o hashing dos pesos das arestas módulo um primo escolhido deterministicamente para minimizar falsos positivos, seguido de uma busca de testemunha.
Cadeia de Reduções: Reduções de granularidade fina conhecidas ligam 3SUM e APSP ao Triângulo Exato. Ao compor essas reduções com o novo algoritmo para o Triângulo Esparso de Todas as Arestas Assimétrico, os autores derivam algoritmos mais rápidos para os problemas originais.

3. Principais Contribuições e Resultados

3.1 Refutação de Hipóteses

O artigo apresenta as primeiras melhorias polinomiais sobre os algoritmos de livro texto para 3SUM e APSP, refutando assim as hipóteses de 3SUM e APSP da complexidade de granularidade fina.

3SUM: Resolvido deterministicamente em $O(n^{1.9992})$ tempo para inteiros de tamanho polinomial.
APSP: Resolvido deterministicamente em $O(n^{2.9995})$ tempo para grafos direcionados com pesos inteiros de limite polinomial.
Triângulo Exato: Resolvido deterministicamente em $O(n^{2.9983})$ tempo.
APSP Não-Ponderado Direcionado: Resolvido deterministicamente em $O(n^{2+\mu-\epsilon})$ tempo (onde $\mu < 0.5275$ ), refutando a hipótese de que o algoritmo de Zwick é ótimo. Esta é a primeira melhoria não derivada puramente de limites de multiplicação de matrizes retangulares mais rápidos.

3.2 Variantes de Valores Reais

Usando uma redução de Chan, Vassilevska Williams e Xu que depende apenas de comparações, adições e subtrações, os autores fornecem algoritmos Las Vegas (randomizados com erro zero) para as versões de valores reais destes problemas:

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

3.3 Impacto Algorítmico Amplo

Através de reduções conhecidas, a nova técnica produz acelerações polinomiais para uma vasta gama de outros problemas, incluindo:

Produto $(\min, +)$ de matrizes.
Distância de Edição de Árvore (para custos de inteiros de limite polinomial).
$k$ -Clique de Peso Zero, Peso Mínimo e Peso Máximo para qualquer constante $k \ge 3$ .
Conjecturas de Vetor-Matriz Online (OMv): O artigo refuta as variantes "com dicas" da conjectura OMv (especificamente para dicas finas) ao fornecer uma estrutura de dados que pré-processa matrizes em tempo subquadrático e responde consultas de entrada única em tempo sublinear em relação à dimensão interna.
Knapsack e Subset Sum Aproximado: Primeiros algoritmos verdadeiramente subquadráticos para Knapsack Ilimitado e esquemas de aproximação para Subset Sum.

3.4 Versão de Estrutura de Dados

Os autores estendem o algoritmo de matriz para uma estrutura de dados. Após o pré-processamento de $X$ e $Y$ em $O(N^2/D^{0.063})$ tempo, qualquer entrada única $(XY)[I, J]$ pode ser computada em $O(D^{0.437})$ tempo. Isso permite resolver problemas onde as entradas alvo não são conhecidas de antemão.

4. Significância e Alegações

Os autores veem este trabalho como um "grande sucesso para a complexidade de granularidade fina".

Reduções como Algoritmos: O artigo enfatiza que as reduções de granularidade fina, anteriormente usadas principalmente para inferir dureza condicional, também são algoritmos. Uma única nova técnica (o algoritmo de produto de matrizes finas) pode acelerar simultaneamente uma vasta teia de problemas interconectados.
Refutando o Status Quo: Os resultados demonstram que os tempos de execução "travados" para 3SUM e APSP não eram barreiras fundamentais, mas sim artefatos das técnicas disponíveis na época.
Limitações e Questões Abertas:
- Os autores observam que suas técnicas não melhoram atualmente o CNF-SAT, Vetores Ortogonais ou $k$ -SUM para $k \ge 4$ , pois esses problemas não se reduzem aos casos específicos de triângulo esparso resolvidos aqui.
- Os algoritmos são algébricos e atualmente possuem grandes constantes ocultas, tornando-os impraticáveis para uso imediato no mundo real.
- O caso equilibrado de Triângulo de Todas as Arestas Esparso (onde todas as três partes têm tamanho $n$ ) permanece não resolvido por esta técnica, mantendo intacta a hipótese $m^{4/3}$ para esse caso específico.
- O artigo não afirma ter encontrado o tempo de execução ótimo para esses problemas, observando que melhorias adicionais são provavelmente possíveis através de melhores reduções ou identidades algébricas refinadas.

5. Nota Metodológica sobre Descoberta

O artigo reconhece explicitamente que o algoritmo central foi descoberto pelo Claude, um modelo de IA desenvolvido pela Anthropic. Os autores (Josh Alman e Virginia Vassilevska Williams) trabalharam para entender, simplificar, fortalecer e estender o algoritmo, derivar consequências e formalizar os resultados. Os principais resultados foram verificados usando o assistente de provas Lean 4. Os autores assumem total responsabilidade pelo conteúdo e apresentação do artigo.