MISTURAR MENSAGENS SUPERA ROTEÁ-LAS, DEPOIS DE 22 ANOS DE DÚVIDA

Imagine uma rede de cabos em que vários remetentes querem, cada um, alcançar o seu próprio destinatário. A abordagem clássica é o roteamento: cada mensagem viaja como uma encomenda por um ou mais caminhos, e o tráfego pode até ser dividido entre muitos caminhos em qualquer proporção. A codificação de rede (network coding) acrescenta uma liberdade a mais: os nós intermediários podem combinar as mensagens que recebem — por exemplo, somando-as — em vez de apenas repassá-las.

A questão é se essa liberdade alguma vez deixa passar mais dados. O artigo se concentra em redes não direcionadas, em que um cabo pode transportar dados em qualquer sentido, mas os dois sentidos compartilham uma única capacidade.

Uma conjectura confirmada caso após caso

Em 2004, Li e Li conjecturaram que, nesse cenário, a codificação não traz vantagem nenhuma sobre o roteamento fracionário; Harvey, Kleinberg e Rasala Lehman formularam a mesma conjectura de forma independente. Nas duas décadas seguintes, ela foi confirmada para uma classe de redes após outra — duas sessões, certas redes planares, redes com no máximo seis nós de codificação, entre outras —, mas nunca resolvida em geral. Outros resultados da teoria da complexidade, como limites inferiores para a ordenação de inteiros em memória externa e para circuitos de multiplicação, tinham até sido provados supondo que ela fosse verdadeira.

A teoria conhecida já limitava o que estava em jogo: a codificação pode superar o roteamento no máximo por um fator logarítmico. E um resultado de 2017 de Braverman, Garg e Schvartzman mostrou que uma única rede com uma vantagem estrita da codificação poderia ser amplificada até uma diferença muito maior. Tudo se resumia a encontrar um exemplo finito.

Somar basta

O apêndice apresenta o dispositivo básico, que mostra por que misturar pode ajudar. Coloque várias fontes em volta de um nó central v, seus destinatários em volta de outro nó central w, e ligue v e w por um cabo. Cada fonte também tem pequenos caminhos laterais até os outros destinatários. Em três rodadas, o cabo do meio transporta a soma de todas as mensagens; cada destinatário recebe essa soma mais as outras mensagens pelos caminhos laterais e recupera a sua por subtração. Sem o cabo do meio, cada fonte fica a cinco saltos do seu destinatário.

Esse dispositivo, de um trabalho anterior de Haeupler, Wajc e Zuzic, torna a codificação mais rápida, mas não, por si só, capaz de transportar mais: um caminho longo ainda pode sustentar um fluxo contínuo (pipeline) de alta taxa.

Um circuito transformado em rede

Xindan Zhang e Baochun Li, da Universidade de Toronto, e Zongpeng Li, da Universidade Tsinghua, encontraram o passo que faltava. Eles transformam um código curto numa computação reversível — um circuito de somas inteiras invertíveis que calcula, copia o resultado e depois desfaz o trabalho intermediário. Em seguida, constroem uma nova rede cujos cabos físicos são os fios desse circuito e dão a cada registrador da computação, inclusive os registradores de rascunho, a sua própria demanda remetente–destinatário.

Uma contabilidade cuidadosa do “tempo” ao longo dos fios faz o resto. Somados sobre todos os fios, os comprimentos coincidem exatamente com as distâncias mínimas que as demandas precisam cobrir. Mas as demandas designadas não conseguem evitar certas portas que custam duas unidades extras. Assim, o roteamento fica necessariamente abaixo da taxa máxima, enquanto o código usa cada cabo exatamente uma vez e, encadeado ao longo de muitos blocos, se aproxima de uma taxa igual a um.

O que foi provado

• Uma rede conexa finita, com cada nó ligado a no máximo três outros e capacidade unitária em cada cabo, na qual um simples código linear binário supera o melhor roteamento fracionário possível. A conjectura de 2004 é falsa.
• A mesma construção com inteiros funciona sobre todo corpo finito e todo grupo abeliano finito não trivial de uma só vez.
• Combinando cópias repetidamente, os autores constroem famílias infinitas de redes em que a codificação se aproxima da taxa máxima enquanto o roteamento cai como uma potência de 1/log n — uma vantagem polilogarítmica.

O artigo não informa o número de nós do seu contraexemplo. Só o seu bloco básico já é um código que dura 13.122 rodadas.

Verificado por máquina

Tanto o contraexemplo finito quanto o teorema das famílias estão formalizados no assistente de provas Lean. Segundo os autores, uma auditoria de 2.472 declarações e 1.755 teoremas mostra que as provas usam apenas os três axiomas padrão do Lean, sem provas incompletas; uma nova verificação independente num ambiente limpo também teve sucesso, embora com o mesmo núcleo do Lean.

O que continua em aberto

Os autores listam três perguntas: o tamanho real da vantagem no seu exemplo finito, se o teto logarítmico conhecido é de fato atingido e se existe um contraexemplo pequeno. A última frase do artigo resume a situação: “A codificação, afinal, ajuda sim em redes não direcionadas; quanto ela pode ajudar ainda está por ver.”

Uso de IA declarado. Uma nota de rodapé afirma que o GPT-6 Astra, da OpenAI, ajudou a desenvolver as provas e o código em Lean.