Donald Knuth publica artigo mostrando como o Claude Opus 4.6 resolveu um problema aberto de combinatória
(www-cs-faculty.stanford.edu)Resumo principal
- Donald Knuth, cientista da computação e autor de 'The Art of Computer Programming (TAOCP)', anunciou que o mais recente modelo de IA, 'Claude Opus 4.6', resolveu um problema aberto de combinatória que ele vinha estudando havia várias semanas.
- No problema de encontrar uma decomposição em ciclos hamiltonianos de um dígrafo, Claude descobriu uma estrutura algorítmica generalizada que funciona por meio de 31 execuções de scripts em Python e de seu próprio loop de feedback.
- Knuth, que no passado havia apontado limitações da IA generativa e mantinha uma postura cética, avaliou este resultado como um "avanço dramático em dedução automatizada e resolução criativa de problemas", sugerindo que irá revisar sua visão anterior sobre IA.
Análise aprofundada
O problema resolvido: decomposição em ciclos hamiltonianos (Hamiltonian Cycle Decomposition)
Knuth estava pesquisando um problema de decomposição em um dígrafo específico enquanto escrevia o próximo volume do TAOCP. Em um grafo com $m^3$ vértices $ijk$, para vértices $0 \le i, j, k < m$, cada vértice possui 3 arcos apontando para $i+jk$, $ij+k$, $ijk+$ (onde $i+ = (i+1) \bmod m$). O objetivo era encontrar uma solução geral (general decomposition) que decompusesse esses arcos em 3 ciclos direcionados de comprimento $m^3$ para todos os casos com $m > 2$. Knuth havia resolvido o caso $m=3$, mas estava encontrando dificuldades para derivar uma fórmula generalizada para valores maiores.
Princípio de implementação e contexto técnico: raciocínio híbrido e loop autônomo de exploração
Filip Stappers, colega de Knuth, inseriu o problema no 'Claude Opus 4.6', o mais recente modelo híbrido de raciocínio da Anthropic. Em vez de fazer uma consulta simples, ele forneceu ao prompt fortes restrições para forçar um workflow agentivo (agentic).
Claude imediatamente redefiniu o problema em termos matemáticos e escreveu scripts em Python (exploreXX.py) para iniciar um loop de validação de hipóteses. Ao longo de cerca de 1 hora, tentou vários algoritmos, como brute force, fiber decompositions e simulated annealing, realizando 31 explorações.
O ponto de virada central da solução
Em especial, na 25ª exploração, Claude analisou a própria limitação e mudou a direção da busca ao concluir que "o algoritmo de simulated annealing pode encontrar soluções individuais, mas não consegue apresentar uma construção matemática geral, portanto é necessária uma abordagem puramente matemática". Por fim, na 31ª exploração, com base nos padrões estruturais das tentativas anteriores, derivou uma estrutura generalizada exata que funciona quando $m$ é ímpar. Com base nesse resultado, Knuth completou a prova matemática e deu a ela o nome de 'decomposições no estilo Claude (Claude-like decompositions)'.
Código e dados principais
A seguir estão as principais restrições (prompt) fornecidas por Filip Stappers ao Claude e parte do log de autoavaliação registrado pelo próprio Claude.
# 1. Restrições de workflow dadas ao Claude (controle de loop e documentação obrigatória)
"""
After EVERY exploreXX.py run, IMMEDIATELY update this file [plan.md] before doing anything else.
No exceptions. Do not start the next exploration until the previous one is documented here.
"""
# 2. Redefinição matemática do problema feita pelo Claude (abordagem inicial)
"""
Need sigma: Z3 m — S3, assigning a permutation of {0,1,2} at each vertex;
cycle c at vertex v goes in direction sigma(v)[c].
Each resulting functional digraph must be a single Hamiltonian cycle.
"""
# 3. Autoavaliação do Claude após a 25ª exploração (mudança de direção)
"""
SA(Simulated Annealing) can find solutions but cannot give a general construction.
Need pure math.
"""
9 comentários
O cara que está nos livros didáticos fica toda hora acrescentando mais coisa aos próprios livros didáticos....
(Reconhecido)
Claro, porque escrever os livros-texto é o papel dele mesmo (assentindo)
kkkkkkk agora ele provavelmente vai adicionar ainda mais com IA
Então o TAOCP ainda ia ganhar mais volumes, né.
Compartilhar exatamente como usou IA para resolver um problema de matemática e ainda escrever o artigo científico no TeX que ele mesmo criou.... absurdamente estiloso
Foi graças à matéria que conheci o TAOCP pela primeira vez; acho que vou dar uma olhada com calma.
Ele ainda está vivo?
Até agora ainda está fazendo correções...