Os ciclos de Claude [PDF]

 (www-cs-faculty.stanford.edu)
4 pontos por GN⁺ 2026-03-04 | 1 comentários | Compartilhar no WhatsApp
  • Claude Opus 4.6, da Anthropic, resolveu o problema da decomposição em ciclos hamiltonianos direcionados que Donald Knuth vinha estudando havia várias semanas
  • O problema consiste em encontrar uma decomposição em três ciclos hamiltonianos de um grafo direcionado com (m^3) vértices, e Claude o resolveu completamente para m ímpar
  • Claude executou em etapas várias estratégias de busca, incluindo decomposição em fibras, padrão serpentino 3D, busca em profundidade (DFS) e simulated annealing
  • Ao final, derivou uma solução geral na forma de um programa em Python, e Filip Stappers a verificou para m ímpar de 3 a 101, confirmando a decomposição completa
  • Knuth avalia o resultado como um avanço revolucionário em raciocínio automatizado e solução criativa de problemas e afirma que o caso de m par continua em aberto

Contexto e definição do problema

  • O tema de pesquisa trata de ciclos hamiltonianos direcionados, e está previsto para um futuro volume de The Art of Computer Programming, de Knuth
  • O grafo é composto por (m^3) vértices (ijk), e de cada vértice saem três arestas: (i+jk), (ij+k), (ijk+)
  • O objetivo é encontrar, para todo (m>2), uma solução geral que decomponha essas arestas em três ciclos direcionados de comprimento (m^3)

Processo de busca do Claude

  • Claude Opus 4.6 é o modelo de raciocínio híbrido da Anthropic; Filip Stappers apresentou o problema e instruiu o modelo a documentar o processo
  • Na etapa inicial, Claude reformulou o problema como um grafo funcional e um problema de atribuição de permutações, e tentou abordagens com funções lineares e quadráticas, mas sem sucesso
  • Depois disso, experimentou sucessivamente busca DFS, análise de padrões serpentinos 2D e padrões baseados em código Gray 3D
  • Em seguida, introduziu a abordagem de decomposição em fibras, analisando uma estrutura estratificada com base em (s = (i+j+k) \mod m), e encontrou soluções parciais por meio de simulated annealing (SA)

Descoberta e verificação da solução

  • Na etapa 31 da busca, Claude gerou um programa em Python usando uma regra dependente de uma única coordenada para cada fibra
  • Esse programa gera três ciclos hamiltonianos completos para m=3,5,7,9,11
  • Filip Stappers o testou para todos os valores ímpares de m entre 3 e 101, confirmando a decomposição completa
  • Knuth simplificou isso em código C e apresentou uma prova matemática de que cada ciclo tem de fato comprimento (m^3)

Generalização e análise matemática

  • Foi confirmado que parte dos ciclos hamiltonianos de m=3 pode ser generalizada para todo m ímpar
    • Em (m=3), entre 11.502 ciclos, 1.012 se generalizam para (m=5), e 996 se generalizam até (m=7)
    • Esses 996 podem ser generalizados para todo m ímpar > 1
  • A decomposição do tipo "Claude-like" é definida por regras simples que dependem apenas dos valores de fronteira de i, j e s (0 ou m−1)
  • Teorema: para que uma decomposição "Claude-like" seja válida para todo m ímpar > 1, os três ciclos em m=3 devem ser ciclos hamiltonianos generalizáveis
  • Segundo os cálculos, 760 decomposições "Claude-like" são válidas para todo m ímpar

O caso em aberto para m par e a conclusão

  • No caso de m par, o problema continua em aberto
    • Estudos anteriores já provaram que (m=2) é impossível
    • Claude encontrou soluções parciais para (m=4,6,8), mas falhou em generalizá-las
  • Durante a exploração de m par, Claude apresentou erros e comportamento anormal, e a busca foi interrompida
  • Knuth avalia isso como uma conquista histórica do raciocínio automatizado baseado em IA e menciona que é um avanço à altura do nome de Claude Shannon

Apêndice: regras dos outros dois ciclos

  • Segundo ciclo (c=1):
    • Se (s=0), j aumenta; se (0<s<m−1), i aumenta; quando (s=m−1), se i>0 então k aumenta, e se i=0 então j aumenta
  • Terceiro ciclo (c=2):
    • Em (s=0), se j<m−1 então i aumenta, e se j=m−1 então k aumenta
    • Em (0<s<m−1), se i<m−1 então k aumenta, e se i=m−1 então j aumenta
    • Em (s=m−1), i aumenta
  • A ordem dos vértices em s=0 de cada ciclo está explicitada, o que permite demonstrar a estrutura do ciclo completo

Leituras relacionadas

1 comentários

 
GN⁺ 2026-03-04
Comentários no Hacker News

  • É interessante pensar em que tipos de problema a escalabilidade de RL pode ser aplicada
    Antes, isso dependia da cognição humana, mas agora esse tipo de padrão está embutido em uma distribuição de probabilidade, então qualquer um pode acessá-lo
    Ainda assim, fica a dúvida se os modelos conseguirão acompanhar à medida que a fronteira da ciência continuar se expandindo
    Em 2030, para a Anthropic manter o Claude atualizado, vai precisar de (a) aprendizado contínuo em um modelo fixo ou (b) treinamento contínuo, e nenhum dos dois é simples

    • Modelos com pesos abertos são como uma espécie de cápsula do tempo
      Depois do ponto de corte de conhecimento, eles ficam presos naquele momento para sempre
    • Se o compartilhamento de dados for permitido, os resultados de inferência de hoje podem virar os dados de treino de amanhã
      Dá até para imaginar um modelo que oferece inferência gratuita a pesquisadores em troca de usar esse rastro de raciocínio (trace) como dado de treino
    • Pelo que pesquisadores vêm dizendo recentemente, parece que a arquitetura dos modelos vai evoluir no sentido de expandir bastante a janela de contexto
      Modelos como Qwen3-next, Qwen3.5 e Nemotron 3 Nano suportam janelas de milhões de tokens com atenção híbrida, reduzindo o custo de memória
    • A maior parte da pesquisa e do aprendizado já está acontecendo por meio de LLMs e agentes de programação
      Loops de feedback em tempo real com validação humana, execução de código e busca funcionam como sinal de treino para os modelos
    • Em 2030, talvez seja o Claude que mantenha a Anthropic atualizada
      É meio brincadeira, mas não é algo totalmente impossível

  • Isso lembra a antiga conversa entre Wolfram e Knuth sobre o GPT-4
    Knuth era cético na época, mas ao ver modelos recentes como o Opus 4.6, parece ter suavizado a postura
    É admirável mudar de ideia diante de novas evidências
    A conversa relacionada pode ser vista aqui

    • Atualizar a probabilidade a priori (prior) com base em novas evidências é justamente o charme da estatística bayesiana
      E também o cerne do pensamento científico

  • A introdução do texto do Knuth parece um tanto passível de interpretação equivocada
    Fica parecendo que o Claude resolveu o problema diretamente, mas na prática o Claude criou exemplos e o Knuth generalizou isso e transformou em prova

    • Eu também fiz experimentos parecidos com o Claude, e a sinergia entre humano e LLM é realmente grande
      LLMs são fracos em definir a direção, mas, uma vez dada a direção, fazem uma exploração profunda muito bem
      Se deixados sozinhos, vão para lugares estranhos, mas, quando uma pessoa lidera, viram ótimos parceiros
    • Não acho que o Knuth tenha superestimado
      O Claude teve o papel de penetrar no cerne do problema, e o humano só refinou isso
    • Também dá para considerar que o Claude fez a ‘solução’ de que o Knuth fala
      Organizar a prova é só um trabalho secundário
    • A capacidade de voltar a tentativas anteriores para refletir e corrigir de fato parece um sinal de inteligência

  • A parte em que o Claude parou no caso par é interessante
    Ele provavelmente usou claude.ai ou claude code, e parece ter entrado numa zona burra por excesso de contexto (dumb zone)

    • Seria bom se desse para visualizar essa dumb zone
      Algo como mostrar um gráfico de uso de contexto como no Copilot, para o usuário perceber isso, seria útil
    • No fim, sem compressão de contexto (compacting), o resultado vira bagunça
    • Como ele menciona um ‘plan document’, parece que estava usando um documento de gerenciamento de sessão
    • Também houve quem perguntasse o que exatamente seria essa dumb zone

  • Alguém testou fazer o Claude resolver o famoso quebra-cabeça de pentominós popularizado por Arthur C. Clarke
    Ao representar o tabuleiro e as peças com inteiros de 64 bits, ele criou um programa em C# que resolveu rápido, mas no caso 20x3 deu uma resposta errada por causa de um mapeamento incorreto
    É interessante porque parece um erro que um humano cometeria

  • Resumindo, Knuth propôs o problema e um amigo fez mais de 30 explorações com o Claude
    O Claude criou um programa em Python que resolve os casos ímpares, e o Knuth provou essa abordagem
    O caso par continua sendo um problema em aberto

    • Mas a expressão “careful human guidance” usada pelo Knuth parece exagerada
      Na prática, o Claude travava ou errava com frequência, e o humano só dava alguns lembretes de vez em quando
    • O que o Knuth parece ter enfatizado é que a prova formal ainda é tarefa humana
      Não fica claro de quem veio a ideia central

  • Hoje em dia é realmente um momento divertido para lidar com problemas em aberto
    Dá vontade de revisitar pesquisas de 10 anos atrás e explorá-las de novo com o Claude

  • Os pontos fortes dos LLMs parecem ser três: conhecimento vasto, capacidade de fazer conexões e tentativa e erro incansáveis
    Quando essas três coisas se juntam, às vezes surgem resultados surpreendentes
    Talvez até a prova de P≠NP esteja em alguma ligação tênue que humanos ainda não perceberam

    • O último item pode na verdade ser menos uma característica do próprio LLM e mais uma característica de um loop de agente
      O LLM é só um dos componentes ali dentro
    • Mesmo assim, a exploração iterativa sem se cansar é uma grande vantagem em relação aos humanos
      Mantidas as demais condições, isso pode ser a diferença decisiva
    • Concordo totalmente que juntar essas três coisas pode gerar resultados incríveis
    • Mas assusta pensar que esse tipo de capacidade possa ser usado em sistemas de vigilância
    • Essa ‘capacidade de fazer conexões’ talvez esteja na prática limitada a conexões que já existem nos dados de treino
      Ainda é difícil criar conexões realmente novas

  • Fico em dúvida se a frase “LLM é só uma máquina de prever a próxima palavra” está mesmo correta
    Se for assim, como explicar esse tipo de resolução de problemas? Isso seria ‘pensar’?

    • Se fosse possível prever perfeitamente qual seria a próxima palavra dita por Einstein, isso já seria implementar inteligência
      A expressão “a palavra mais provável” é uma simplificação excessiva
    • Essa explicação vale para o modelo base, mas modelos como o Opus 4.6 têm RLHF e treinamento adicional por cima
      No fim, a própria “capacidade de prever bem o que vai acontecer em seguida” talvez seja a definição de inteligência
    • O modelo base aprende naturalmente padrões de resolução de problemas ao absorver o padrão “Answer:” da web
      Graças ao RLHF, ele é recompensado não por prever qualquer coisa, mas por dar respostas úteis
      É por isso que expressões como “delve” aparecem com frequência excessiva
      Veja também o documento AI SIGNS
    • No fim, ainda se trata de escolher palavras a partir de uma distribuição de probabilidade, mas essa distribuição em si é o núcleo da inteligência
      Os LLMs estão aprendendo essa distribuição
    • Quando o mecanismo simples de “a palavra mais provável” se combina com o conhecimento acumulado de toda a humanidade, ele ganha um poder imenso
      Reduzir isso a uma caricatura irônica é perder de vista a essência da tecnologia

  • É interessante ver que é um relatório do próprio Knuth
    É hora de ler e entender isso sem ajuda de LLM

    • Como não tive tempo, procurei em vez disso um link de resumo feito por alguém