CAI UMA BARREIRA DE 1962 NA CIÊNCIA DA COMPUTAÇÃO

Um ciclo hamiltoniano é uma viagem de ida e volta por uma rede que visita cada ponto exatamente uma vez e retorna ao início. Numa rede direcionada, cada ligação é uma seta que só pode ser percorrida num sentido, como uma rua de mão única. A versão ponderada desse problema é o problema do caixeiro-viajante assimétrico.

Decidir se tal ciclo existe é um problema difícil de manual. Em 1962, Richard Bellman e, de forma independente, Michael Held e Richard Karp apresentaram algoritmos de programação dinâmica que o resolvem em tempo de cerca de 2ⁿ para uma rede de n pontos (a menos de fatores que crescem apenas polinomialmente). Por mais de sessenta anos, ninguém conseguiu fazer fundamentalmente melhor em redes direcionadas gerais.

O primo não direcionado já tinha caído

Para redes com ligações de mão dupla, Andreas Björklund quebrou a barreira em 2014 com um algoritmo aleatorizado que roda em 1,657ⁿ, trabalho que lhe valeu o Prêmio Nerode EATCS–IPEC de 2016, segundo o artigo. Ele ainda é o mais rápido conhecido para redes não direcionadas gerais. Para as direcionadas, o progresso veio apenas em casos especiais — redes bipartidas, redes com poucas ligações por ponto — ou sob uma hipótese não provada, a conjectura do posto assintótico de Strassen.

O novo limite

Tomohiro Koana, da Universidade de Tóquio, e Soh Kumabe, da empresa CyberAgent, de Tóquio, apresentam agora um algoritmo aleatorizado que decide o problema direcionado em tempo

O((375/196)ⁿ) = O(1,9133ⁿ)**.

Para redes direcionadas gerais, é a primeira melhoria na base da exponencial desde 1962.

Contando em ímpar e par

A dificuldade é sutil. Contar ciclos módulo 2 — saber apenas se seu número é ímpar ou par — já era possível abaixo de 2ⁿ. Mas um número par e não nulo de ciclos parece exatamente igual a zero. A solução clássica é dar pesos aleatórios às ligações para que, em algum peso total, uma solução se torne única (o lema do isolamento); mas o método rápido de contagem de paridade não conseguia lidar com pesos.

A receita dos autores, em palavras simples:

1. Adivinhar uma seta do ciclo e procurar, em vez disso, um caminho que passe por todos os pontos, de uma ponta dessa seta à outra.
2. Apagar cada seta aleatoriamente com probabilidade 1/50.
3. Em cada ponto, criar três grupos de setas de entrada e copiar cada seta sobrevivente para um conjunto aleatório não vazio de grupos.
4. Se existir um circuito, então com probabilidade de pelo menos (49/50)ⁿ⁻¹ é possível escolher um grupo por ponto de modo que o número de caminhos válidos seja ímpar.
5. Dar a cada grupo — e não a cada seta — um peso aleatório. Agora o truque do isolamento funciona, e cerca de (50/49)ⁿ repetições bastam.
6. Cada repetição calcula as contagens de ímpar ou par em cada peso total em tempo (15/8)ⁿ, usando somas de determinantes de matrizes devidas a Björklund, Kaski e Koutis e uma “linearização” aleatória também usada por Arvind e Guruswami.

Multiplicando os dois: (50/49)ⁿ × (15/8)ⁿ = (375/196)ⁿ ≈ 1,9133ⁿ.

Uma prova gerada por uma máquina

O artigo termina com uma declaração sobre IA generativa: o ChatGPT 6 Astra gerou a prova do teorema principal e ajudou a redigir o manuscrito. Os autores forneceram os enunciados das proposições intermediárias, que dão uma leitura combinatória da solução original do modelo, depois verificaram e revisaram tudo e assumem total responsabilidade.

O resultado é teórico — nenhum programa foi executado — e o algoritmo é aleatorizado, com uma pequena chance de erro em qualquer sentido. Entre 1,9133 para ruas de mão única e 1,657 para as de mão dupla, uma grande lacuna continua em aberto.