GPT-5.6 e a conjectura de Dinitz-Garg-Goemans

Em 22 de julho de 2026, Dmitry Rybin publicou no X uma afirmação que fez um certo tipo de pessoa largar o café: o GPT-5.6 Pro teria produzido um contraexemplo para a conjectura de Dinitz-Garg-Goemans, em aberto na otimização combinatória há cerca de 30 anos. A prova de conceito era um grafo pequeno. Custo do fluxo fracionário 58, custo do fluxo não fracionável 60. Dois pontos, três décadas, quatro prompts.

A maior parte da cobertura repete os números sem mostrar o mecanismo por trás deles — e é no mecanismo que mora a lição de verdade. Também é onde preciso ser direto com você sobre o que foi verificado e o que não foi. Versão curta: os conceitos são sólidos, a notícia é uma alegação e ainda não um teorema, e se você sentar para reproduzir do zero o grafo exato, vai entender por que problemas assim são difíceis no instante em que a sua reconstrução começa a vazar.

A resposta rápida

Rybin relata que o GPT-5.6 Pro, guiado por quatro prompts com menos de 60 palavras no total, produziu um contraexemplo para a conjectura de custo de Goemans, um problema em aberto desde mais ou menos 1999. Seu caso é um grafo direcionado pequeno com uma única origem e três destinos. Ele afirma que o roteamento fracionável (splittable) custa 58, enquanto qualquer roteamento não fracionável que mantenha a congestão dentro do orçamento permitido custa pelo menos 60. Essa diferença de dois pontos, se resistir à revisão formal, basta para derrubar a conjectura.

Ainda não passou por revisão por pares. Rybin publicou toda a conversa no ChatGPT para que qualquer um leia a construção, e várias pessoas checaram a aritmética e acharam consistente. Aritmética reprodutível e prova aceita são coisas diferentes, porém — e a distância entre elas é toda a história deste artigo.

O que é a conjectura de Dinitz-Garg-Goemans?

Antes de entender o que caiu — ou pode ter caído —, precisamos entender o que a conjectura de fato diz.

Imagine um centro de distribuição enviando pedidos para três cidades por uma rede de estradas. Se você pode dividir um envio, dá para mandar metade do pedido por uma estrada e metade por outra. Isso é roteamento fracionário, e é flexível; geralmente encontra um conjunto de caminhos mais barato. Mas muita carga real não pode ser dividida. Um pedido, um caminhão, uma estrada, do início ao fim. Isso é fluxo não fracionável, e é o que um pedido de frete, um pacote de rede ou um contêiner realmente precisa fazer.

A pergunta que se discute desde 1999 é simples de enunciar. Se existe um roteamento fracionável barato, será que você sempre consegue encontrar um roteamento não fracionável que também seja barato sem sobrecarregar demais as estradas?

Yefim Dinitz, Naveen Garg e Michel Goemans resolveram metade disso. A outra metade é a parte que o GPT-5.6 atacou. Para entender por que essa distinção importa tanto, precisamos ser precisos.

O teorema vs. a conjectura

Essa é a distinção que muitos textos confundem, então vou ser preciso uma vez e depois me apoiar nisso pelo resto do artigo.

Dinitz, Garg e Goemans provaram um resultado de congestão: dado um fluxo fracionário válido, você sempre pode convertê-lo em um não fracionável sem ultrapassar a capacidade de nenhuma estrada por mais do que a maior demanda individual, chame esse número de D. Esse teorema não está em questão e nunca esteve.

O que Goemans, separadamente, conjecturou é a versão mais forte, sensível a custo: que a mesma conversão conseguiria manter o custo total baixo ao mesmo tempo em que mantém a congestão baixa. Congestão e custo, ambos limitados, em um único roteamento. O teorema apenas de congestão está seguro. A conjectura de custo + congestão é a peça que Rybin diz ter caído. Se você for levar uma frase deste texto, que seja essa. Muito do entusiasmo por aí troca as duas silenciosamente, e a diferença entre elas é justamente a lacuna matemática que levou 30 anos para fechar.

O que o GPT-5.6 realmente construiu

O caso de Rybin é pequeno o bastante para caber em um parágrafo. Uma origem, alguns nós intermediários formando uma “espinha” compartilhada e três destinos, cada um com uma demanda. Cada destino tem duas opções: um caminho direto e caro, ou um desvio gratuito pela espinha compartilhada.

A tensão é estrutural. Os desvios baratos competem por espaço na espinha, então, se destinos demais tentam roteamentos baratos ao mesmo tempo, uma estrada da espinha estoura. Forçando o bastante, apenas um destino consegue pegar o caminho barato em qualquer roteamento não fracionável válido. O restante é empurrado para os caminhos diretos e caros, e o custo sobe. Já o fluxo fracionário, livre para dividir, espalha cada demanda pelos dois caminhos e passa por baixo de toda capacidade de uma vez. É assim que você consegue um custo fracionário abaixo do menor custo não fracionável legal. Os números de Rybin para o seu caso são 58 e 60.

Vou ser honesto sobre um limite aqui. Não consegui reproduzir o grafo exato de Rybin — as capacidades específicas e os conflitos par a par — a partir de uma fonte primária. Sua transcrição descreve um ponto particular em uma família de parâmetros, e a descrição “de sete nós” amplamente compartilhada é uma abstração disso, não uma construção que eu tenha verificado aresta por aresta. Então não vou encenar uma derivação arrumadinha do 58 e fingir que é dele. O que eu posso fazer é te entregar um caso autocontido que mostra o mesmo mecanismo, pequeno o suficiente para checar por força bruta, para você ver com seus próprios olhos como é quando “o fracionário vence todo não fracionável legal”. 

Quatro prompts, várias horas

A contagem de prompts é a parte menos interessante desta história — embora seja a que viralizou.

O log do chat compartilhado por Rybin mostra o modelo falhando primeiro, e falhando com precisão. O prompt inicial pediu um contraexemplo estruturado. Ele trabalhou por quase uma hora e voltou de mãos vazias, afirmando abertamente que apresentar o que tinha como contraexemplo válido seria falso.

Ao ser instruído a continuar, rodou de novo e, outra vez, não trouxe nada, descrevendo como cada construção promissora sempre revelava uma rota extra escondida que destruía a separação custo–congestão quando todos os caminhos eram enumerados. Um terceiro prompt pedindo uma estratégia mais limpa rendeu uma estrutura mais estreita e ainda assim nenhum resultado final.

Isso não é “quatro prompts e pronto”. São horas de um modelo batendo em paredes e dizendo a verdade sobre elas. A parede específica em que ele batia — surge uma rota extra e arruína a separação — é exatamente o que a construção final foi projetada para evitar, prendendo cada destino a exatamente dois caminhos, de modo que todo o espaço de roteamento seja oito opções que você pode enumerar na mão. Guarde esse modo de falha em mente. Você está prestes a esbarrar nele também.

O quarto prompt, supostamente algo próximo de “já deu de fracassar, por favor conclua com um contraexemplo completo e incondicional”, foi o que produziu a construção funcional, junto com certificados de prova, um programa de enumeração e LaTeX completo. A paciência fez diferença. As recusas anteriores também; foram autoavaliações honestas.

Confira você mesmo

Aqui é onde a cobertura da DataCamp pode fazer algo que um post de notícias não consegue: deixar você rodar a verificação.

Um alerta rápido antes do código. O que vem a seguir não é o grafo de Rybin. É um caso esquemático que construí para ser honesto: cada destino realmente tem exatamente duas rotas, a aritmética fecha e a diferença é real. Ele mostra o formato de um contraexemplo assim e a técnica para checar um. Sozinho, não refuta nada, e vou explicar por quê logo depois que você rodar.

O setup: três destinos, cada um enviando 10 unidades, então a maior demanda D é 10. Cada um tem um caminho direto caro (custo 30) e um caminho barato gratuito. Os caminhos baratos são organizados de forma que cada par deles dispute um gargalo particular: a estrada A é compartilhada pelos destinos 1 e 2, a estrada B pelos destinos 1 e 3, e a estrada C pelos destinos 2 e 3. No fluxo fracionário, cada destino envia 2/5 da sua demanda pelo barato e 3/5 pelo caro, o que custa 30 x 3/5 x 3 = 54. Cada estrada então carrega 4 + 4 = 8 unidades fracionárias, e o orçamento de congestão é essa carga mais D, portanto 18.

Agora veja o que o roteamento não fracionável faz com isso. Dois destinos indo pelo barato despejam 10 + 10 = 20 unidades na estrada que compartilham, acima do orçamento de 18. Então, no máximo um destino pode roteá-lo barato; os outros dois pagam 30 cada. Custo mínimo não fracionável legal: 60. Contra um fracionário de 54. Existem oito roteamentos, então basta checar todos:

from itertools import product
	
# Three terminals, demand 10 each -> largest demand D = 10.
# Each has a cheap path (cost 0) and an expensive direct path (cost 30).
# Cheap paths pairwise share a PRIVATE bottleneck road, so every pair conflicts:
#   road A shared by {t1, t2},  road B by {t1, t3},  road C by {t2, t3}
# NOTE: this is a schematic instance to illustrate the check, not Rybin's graph.

demands = [10, 10, 10]
d_max = max(demands)          # congestion slack allowed on each road
cheap_frac = [2/5, 2/5, 2/5]  # expensive fraction is 3/5 each -> fractional cost 54
direct_cost = 30              # cost of one terminal's expensive path

# Which bottleneck roads each terminal's cheap path uses
uses = [
    {"A": True,  "B": True,  "C": False},  # t1: A, B
    {"A": True,  "B": False, "C": True},   # t2: A, C
    {"A": False, "B": True,  "C": True},   # t3: B, C
]

# The fractional flow saturates each road, so its load is that road's capacity
cap = {"A": 0.0, "B": 0.0, "C": 0.0}
for i in range(3):
    for road in cap:
        if uses[i][road]:
            cap[road] += cheap_frac[i] * demands[i]   # 8 units on each road

# Congestion rule: an unsplittable flow may exceed capacity by at most D
threshold = {road: cap[road] + d_max for road in cap}  # 18 on each road

fractional_cost = sum(direct_cost * (1 - cheap_frac[i]) for i in range(3))  # 54

print(f"Capacities (fractional load): {cap}")
print(f"Congestion budget per road  : {threshold}")
print(f"Fractional flow cost        : {fractional_cost}\n")
print(f"{'Route (0=cheap,1=exp)':22} {'Cost':>4} {'A':>3} {'B':>3} {'C':>3}  Valid")

valid_costs = []
for choices in product([0, 1], repeat=3):    # 0 = cheap, 1 = expensive
    cost = sum(direct_cost * c for c in choices)
    load = {"A": 0, "B": 0, "C": 0}
    for i, expensive in enumerate(choices):
        if expensive == 0:                    # this terminal takes its cheap path
            for road in load:
                if uses[i][road]:
                    load[road] += demands[i]
    ok = all(load[road] <= threshold[road] for road in load)
    tag = "OK" if ok else "overload"
    print(f"{str(choices):22} {cost:>4} {load['A']:>3} {load['B']:>3} {load['C']:>3}  {tag}")
    if ok:
        valid_costs.append(cost)

print(f"\nMin valid unsplittable cost: {min(valid_costs)}")
print(f"Gap: {min(valid_costs) - fractional_cost} (counterexample if > 0)")

Rodando, você obtém custo fracionário 54, custo mínimo não fracionável legal 60 e uma diferença de 6. As três linhas com sobrecarga são os três conflitos par a par; os únicos roteamentos que sobrevivem mantêm no máximo um destino no barato.

Então a conjectura morreu? Ainda não — e esta é a parte que prometi explicar. Aquela enumeração de oito linhas só diz a verdade se cada destino realmente tiver duas rotas e nada mais. Construa esse grafo com estradas e nós de verdade e uma quarta rota barata tende a aparecer pela combinatória. Um destino encontra um terceiro caminho de volta que é barato e fica dentro do orçamento, e a diferença desaparece. Essa rota extra é exatamente a falha que o modelo relatou nas três primeiras tentativas. Um “gadget” limpo e simétrico que derruba uma conjectura de 30 anos em oito linhas de Python seria bom demais para ser verdade — e é. O código acima prova que a verificação é sólida e que a propriedade-alvo é real. Saber se um grafo específico realmente tem essa propriedade, sem vazamentos, é a parte difícil — e é por isso que o caso real de Rybin é um ponto ajustado em uma família de parâmetros e não um triângulo bonitinho.

O que ainda não está resolvido

Nenhum artigo formal foi publicado. Rybin compartilhou a conversa e a construção; nenhum dos dois passou pelo processo de arbitragem que permitiria à comunidade matemática encerrar oficialmente a conjectura.

O grafo exato divulgado não foi reconstruído de forma independente a partir de uma fonte primária que eu tenha encontrado. Os números em circulação vêm do post dele e da transcrição compartilhada. Vários pesquisadores checaram sua aritmética e a consideraram consistente, e um mostrou que seu caso está dentro de uma família infinita de três parâmetros nos mesmos nós, o que tornaria o resultado mais rico do que uma coincidência de sorte. Animador, mas isso é checagem informal da comunidade, não um parecer de árbitros. Trate o 58 vs. 60 como uma alegação bem embasada, não como fato consumado.

O teorema de congestão de 1999 permanece intocado por tudo isso.

Parte de um padrão

Essa história não é um ponto isolado. É a terceira conjectura que teria caído com assistência de IA em cerca de três meses — e esse padrão merece atenção.

Em 20 de julho, o Claude Fable 5 teria ajudado o matemático Levent Alpöge a encontrar um contraexemplo para a conjectura Jacobiana, um problema de 87 anos. Antes, em maio, teria sido um modelo da OpenAI a derrubar a conjectura da distância unitária de Erdős, de 80 anos. Na mesma semana desta notícia, um doutorando da Columbia usou o GPT-5.6 com um workflow estruturado no Codex para resolver seis problemas em aberto de Erdős em cinco dias. O fio condutor, como disse um pesquisador, é que esses sistemas são melhores em refutar do que em provar. Um contraexemplo é uma única testemunha que você consegue checar; uma prova precisa cobrir todos os casos. Essa assimetria parece decidir quais problemas caem primeiro.

A conclusão prática não é “a IA resolve a matemática”. O que estamos vendo é a IA atuando como parceira de busca paciente e combinatoriamente exaustiva: capaz de enumerar famílias de parâmetros, manter modos de falha na memória de trabalho entre tentativas e dizer a verdade quando uma construção não fecha. É uma capacidade específica e útil. E, se você quiser entender onde ela deve acertar na próxima, a pergunta não é quais conjecturas são mais antigas, mas quais podem ser quebradas por uma única testemunha verificável.