O LIMITE DE VELOCIDADE PARA ENCONTRAR CLIQUES CAI DEPOIS DE 40 ANOS
Imagine uma rede social com n pessoas. Existe um grupo de k delas em que todas se conhecem? Os cientistas da computação chamam esse grupo de k-clique, e encontrar uma é um problema clássico com inúmeras aplicações. A abordagem ingênua verifica cada grupo possível de k pessoas, aproximadamente n^k deles — algo inviável para redes grandes.
Um truque de 1985 e um longo desafio
Há mais de 40 anos, Jaroslav Nešetřil e Svatopluk Poljak encontraram um atalho. Eles transformaram a busca por uma k-clique na busca por um triângulo num grafo maior, o que, por sua vez, pode ser feito multiplicando matrizes, grandes tabelas de números. O custo depende de ω, o expoente da multiplicação de matrizes: o método leva cerca de n^(ωk/3) passos. Ninguém conhece ω exatamente. Ele vale pelo menos 2, e o artigo cita um limite superior recente de 9/4.
O expoente desse método de 1985 nunca foi superado. Em 2004, Gerhard Woeginger desafiou os pesquisadores a fazer melhor para algum k fixo; mais de duas décadas se passaram. Enquanto isso, a Hipótese da k-Clique (k-Clique Hypothesis) — de que n^(ωk/3) é essencialmente o melhor possível — tornou-se um alicerce da “complexidade de granularidade fina” (fine-grained complexity). Pesquisadores a usaram para argumentar que muitos outros problemas, da análise sintática de gramáticas à análise de dados comprimidos, também não poderiam ser resolvidos mais rápido.
Um alvo móvel
Refutar essa hipótese tinha uma dificuldade especial. O custo que ela prevê depende de ω, que é desconhecido. Um algoritmo que supera o melhor valor atual de ω poderia deixar de superar a hipótese se alguém mais tarde encontrasse uma multiplicação de matrizes mais rápida.
Virginia Vassilevska Williams, do MIT, e Or Zamir, da Universidade de Tel Aviv, contornam o problema. A dupla prova que, para todo k suficientemente grande, uma k-clique pode ser encontrada — e até contada — em cerca de n^((ω/3 − c)k) passos, onde c é uma constante positiva que não depende nem de k nem de ω. A economia é medida em relação ao verdadeiro valor de ω, seja ele qual for. Ela se mantém mesmo se ω = 2, o melhor caso concebível.
Dobrando uma cunha
O cerne do método diz respeito a padrões de nove vértices. A abordagem padrão os divide em três grupos de três e multiplica três matrizes enormes. Os autores examinam uma cunha (wedge) — duas arestas que compartilham um vértice — e inserem, entre duas das matrizes, uma tabela que não muda nada: a identidade. Em seguida, escrevem essa identidade como uma soma de algumas “trocas” (swaps), cada uma das quais funde as duas arestas da cunha numa só, mais um resto de posto baixo.
As trocas dão padrões mais simples, com menos arestas, tratados de novo pelo mesmo método; um padrão de nove vértices tem no máximo 36 arestas, então a recursão termina. O resto de posto baixo reduz as matrizes a multiplicar. É aplicar o truque a duas cunhas separadas ao mesmo tempo que garante um ganho mesmo quando ω = 2. Qualquer k múltiplo de nove pode então ser agrupado em nove blocos.
Real, mas minúsculo
Os autores não dão números para o ganho. Eles descrevem as constantes como variando “entre ínfimas sem otimização e minúsculas com otimizações significativas”. O ponto não é a velocidade na prática: é que uma barreira em que se acreditou por décadas não existe.
As consequências vão além das cliques. Algoritmos exatos para problemas de otimização difíceis como Max-Cut e Max-2-SAT, que rodavam em cerca de 2^(ωn/3) passos para n variáveis, agora também ganham um expoente menor. O mesmo vale para contar cópias de qualquer grafo pequeno fixo.
O que a IA fez
Numa seção dedicada, os autores descrevem como trabalharam com o ChatGPT-6, usado por meio de sua interface web pública. Partindo de suas próprias ideias para cliques de cinco pessoas e de um resultado recente da OpenAI que refuta outra conjectura, a Hipótese do Tempo Exponencial (Exponential Time Hypothesis), o modelo encontrou uma primeira melhoria, complicada, para as 5-cliques. Os autores então a destilaram, com a ajuda da IA, na decomposição algébrica que está no cerne da prova, que consideram “quase puramente a contribuição da IA”. O arcabouço algorítmico construído em torno dela é, segundo eles, principalmente deles.
Uma observação se destaca. Provas obscuras geradas por IA são difíceis de ler para humanos, observam os autores — e dizem ter se impressionado ao ver que “também são difíceis de entender para a própria IA”.
