Computação e IAPré-publicaçãoTeoria3 min de leitura

ORDENAR COM COMPARAÇÕES PROIBIDAS, QUASE TÃO RÁPIDO

Para colocar n itens em ordem comparando-os dois a dois, cerca de n log n comparações são ao mesmo tempo necessárias e suficientes. Mas isso supõe que quaisquer dois itens possam ser comparados.

Muitas vezes não podem. Os autores tomam emprestado um exemplo de um artigo de 2011: vários candidatos se inscrevem para a mesma vaga, cada um com referências. Dois candidatos só podem ser comparados se alguma referência conhecer os dois. As comparações permitidas formam uma rede, um grafo: cada item é um ponto, cada comparação permitida, uma ligação. A ordem verdadeira está oculta, mas há a garantia de que o grafo a contém, como um caminho que liga cada item ao seguinte. A pergunta: quantas comparações são necessárias para recuperar a ordem? Esse é o problema da ordenação generalizada (generalized sorting).

Por que os truques habituais falham

Os algoritmos clássicos dependem da liberdade de escolha. O QuickSort escolhe um “pivô” e o compara com a maioria dos outros itens, mas um grafo arbitrário pode não ter nenhum item ligado à maioria dos outros. O MergeSort divide os itens em grupos e ordena cada um, mas um grupo pode não ser ordenável sozinho: dois itens vizinhos na ordem final não precisam estar ligados dentro dele. Mais fundamentalmente, a ordenação comum sempre tem à disposição uma comparação que descarta uma boa parte das ordens possíveis; com comparações restritas, pode não haver nenhuma.

O progresso foi lento. Em 2011, Zhiyi Huang, Sampath Kannan e Sanjeev Khanna encontraram um método que usa cerca de n¹·⁵ comparações, a menos de fatores logarítmicos, e esse limite se manteve desde então para grafos arbitrários. Eles chegaram a perguntar se o problema poderia ser fundamentalmente mais difícil que a ordenação comum, exigindo n elevado a uma potência acima de 1.

Prever primeiro, consertar depois

Sanjeev Khanna, da Universidade de Nova York, Aaron Putterman, da Universidade Harvard, e Junkai Song, também da Universidade de Nova York, agora respondem a essa pergunta: não. Seu algoritmo aleatorizado ordena com cerca de n log⁴ n comparações em média, em qualquer grafo — apenas alguns fatores logarítmicos acima da ordenação comum. E, segundo eles, é “relativamente simples”. O ganho, porém, é teórico: as constantes da prova são enormes (fatores como 2³²), então a vantagem só aparece para n muito grande.

Ele se apoia num resultado conhecido: se alguém lhe entrega um palpite sobre o sentido de cada ligação, errado em w delas, a ordem pode ser recuperada com cerca de n log n + w comparações. Assim, a tarefa passa a ser produzir um palpite com poucos erros usando poucas comparações. Os passos-chave:

  • Um primeiro palpite grosseiro. Comparar uma amostra aleatória de pares ligados e escolher qualquer ordem compatível com as respostas. Ele comete muitos erros, mas não demais.
  • Isolar os erros, em vez de corrigi-los. Em vez de corrigir os palpites errados, o algoritmo encontra partes do grafo onde os erros são mais densos que a média e as deixa de lado. Cada rodada reduz os erros restantes, em valor esperado, por um fator de quatro.
  • Voltar depois. As ligações deixadas de lado são tratadas numa fase posterior. Cada fase resolve pelo menos metade das ligações ainda pendentes, então cerca de vinte fases bastam para um milhão de ligações.

Uma prova encontrada com máquinas

A declaração do artigo sobre o uso de IA é incomumente detalhada. Ela afirma que o ChatGPT 6-Astra “foi essencial para provar os limites aprimorados”. Um modelo encontrou primeiro um algoritmo que usava cerca de n¹·³³ comparações, e depois empacou. Os autores o levaram a n¹·²; em seguida, solicitados dezenas de vezes ao longo de várias semanas, modelos encontraram melhorias sucessivas — n^(10/9), n^(17/16), n^(19/18) — antes de chegar ao algoritmo quase linear. Os autores acrescentam que não está claro se o próprio passo intermediário deles foi essencial para essa descoberta final.

O que continua em aberto

O resultado conta comparações, não tempo de computação: tal como está formulado, o algoritmo não roda em tempo polinomial, enquanto o método de 2011 rodava. Os autores listam três perguntas em aberto: se os fatores logarítmicos restantes podem ser eliminados, se um algoritmo sem aleatoriedade consegue fazer o mesmo, e se um algoritmo eficiente consegue atingir o mesmo número de comparações — ou sequer superar n¹·⁵.