10 Agentes Opus 5.5 Descobrem Algoritmo de Caminho Mais Curto que Supera Dijkstra em 15 Horas

O problema do caminho mais curto é um desafio clássico na teoria dos grafos, fundamental para navegação moderna, roteamento de internet, logística e inúmeras outras aplicações reais. Em 1959, o cientista da computação holandês Edsger Dijkstra propôs um algoritmo com complexidade O(m + n log n), que permaneceu como padrão ouro pelos 65 anos seguintes e foi usado ubiquitariamente.

Em 2025, uma equipe da Universidade Tsinghua, Stanford e do Instituto Max Planck finalmente superou esse limite com uma cota de O(m log^{2/3} n). No entanto, a vantagem dessa solução só se manifesta em grafos suficientemente densos (onde o número de arestas m ≥ o número de vértices n). Em grafos esparsos, o algoritmo de Dijkstra continuava sendo superior.

A Vals AI decidiu testar o novo modelo Opus 5.5 especificamente nessa faixa não quebrada (post no blog). Eles lançaram 10 agentes, atribuíram-lhes a tarefa e forneceram um "quadro de avisos" para que trocassem ideias e cooperassem.

Como resultado, dentro de 15 horas e 733 mensagens, os agentes derivaram o algoritmo C-HD e o verificaram formalmente. Esta é a primeira melhoria comprovada especificamente na zona esparsa onde Dijkstra ainda era o melhor: em m ≈ n·log^{3/4}n, o C-HD atinge O(n·log^{11/12}n) comparado ao O(n log n) de Dijkstra. Para n = 2^1000, o ganho é aproximadamente 1,78x e cresce com o tamanho do grafo.

No entanto, apesar da afirmação impressionante e da existência de uma prova em Lean, ainda não há discussão sobre aceleração prática, pois as estimativas acima são assintóticas. O algoritmo ainda não foi benchmarked em grafos do mundo real. Em outras palavras, embora uma curva seja garantida para ultrapassar a outra quando n → ∞, o ponto de cruzamento na prática pode ocorrer apenas em valores enormes de n, e em qualquer grafo realista, Dijkstra provavelmente ainda será mais rápido, apesar de ter assíntoticas piores. Essa parte permanece por verificar.