O problema, o cientista da computação e a IA

• A lenda viva Don Knuth definiu a teoria dos algoritmos como a conhecemos
• Cientista ficou alegre ao ver uma IA resolvendo um problema que formulara 30 anos atrás e no qual trabalhava

"Choque! Choque!"

Don Knuth, do Departamento de Ciência da Computação da Universidade Stanford é uma lenda viva. 

É o autor de "A Arte de Programar Computadores", monumental série de livros (cinco volumes até hoje) que iniciou nos anos 1960 e, efetivamente, definiu a teoria dos algoritmos como a conhecemos. 

Não menos impactante, criou o TeX, a linguagem de editoração usada por 10 em cada 10 matemáticos, engenheiros, físicos, cientistas da computação etc. na preparação de seus trabalhos (50% a 70% de todas as publicações científicas, em todas as áreas, são escritas em TeX!).

Aos 88 anos, com todas essas realizações, talvez não fossem de esperar dele reações emotivas na pesquisa. Mas é exatamente assim que Knuth começa seu trabalho mais recente, datado de 28 de fevereiro: "Choque! Choque!". 

Não é para menos: acabava de saber que um problema matemático que formulara 30 anos atrás, e no qual vinha trabalhando, acabava de ser resolvido. 

"Não por um estudante de doutorado. Não por um grupo de pesquisa. Não por um departamento de matemática. Por um sistema de IA (inteligência artificial)".

Esse problema pertence a uma área da matemática, a teoria dos grafos, que lida com objetos especialmente simpáticos: um grafo é, simplesmente, um conjunto de pontos ligados por linhas. 

Ele pode existir em 2D (pense que os pontos são cidades e as linhas são estradas) ou 3D (por exemplo, os pontos são planetas e as linhas são rotas viáveis). 

O problema em causa tem a ver com encontrar percursos fechados passando por cada ponto do grafo exatamente uma vez ("ciclos hamiltonianos") no grafo cúbico NxNxN.

O caso N=2 é impossível. Knuth resolveu N=3, e o amigo Filip Stappers tratou os casos seguintes até N=16. Foi então que Stappers decidiu submeter o desafio à IA Claude Opus 4.6, da Anthropic. 

O resultado: em 1 hora, Claude produziu um código em linguagem Python que calcula uma solução correta para todo valor ímpar de N. Mas o mais incrível não é o fato da IA ter resolvido o problema: é o modo como o fez!

Stapper informou o enunciado à IA em linguagem matemática usual (bem técnica!) e deu instruções taxativas: "Após TODA tentativa, atualize IMEDIATAMENTE o arquivo de documentação, antes de fazer qualquer outra coisa. 

Sem exceções. Não comece nova tentativa até que a anterior esteja completamente documentada". Assim, dispomos de relato detalhado dos esforços sucessivos de Claude na busca da solução.

O que mais impressiona é que não tem a menor cara de força bruta computacional. 

Pelo contrário, Claude parece raciocinar exatamente como um matemático humano: testando diferentes ideias, abandonando as que não funcionam, aprimorando as mais promissoras e, aos poucos, melhorando sua compreensão do que realmente importa no problema. 

A partir da 15ª rodada, dá para sentir que está "farejando" o caminho certo. Mas ainda há muito a fazer: a solução chega, enfim, na 31ª tentativa.

A reação de Knuth? "Que alegria, não só saber que a minha conjectura tem uma solução linda, mas também comemorar este avanço dramático na área de dedução automática e resolução criativa de problemas. Estamos vivendo tempos realmente interessantes!"

MARCELO VIANA - diretor-geral do Instituto de Matemática Pura e Aplicada, ganhador do Prêmio Louis D., do Institut de France