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 está a verdadeira lição. Também é onde preciso ser transparente com você sobre o que foi verificado e o que não foi. Versão curta: os conceitos são sólidos, a novidade é uma alegação e ainda não um teorema, e quando você se senta para reproduzir exatamente o grafo do zero, entende por que problemas assim são difíceis no momento em que sua reconstrução começa a vazar.

A resposta rápida

Rybin relata que o GPT-5.6 Pro, guiado por quatro prompts somando menos de 60 palavras, produziu um suposto contraexemplo para a conjectura de custo de Goemans, um problema em aberto desde aproximadamente 1999. A instância dele é um pequeno grafo direcionado com uma única origem e três terminais de entrega. Ele afirma que o roteamento fracionável (splittable) custa 58, enquanto qualquer roteamento não fracionável (unsplittable) que mantenha a congestão dentro do orçamento permitido custa pelo menos 60. Esse gap de dois pontos, se resistir a uma revisão formal, é suficiente para derrubar a conjectura.

Ainda não passou por revisão por pares. Rybin publicou toda a conversa no ChatGPT para que qualquer pessoa possa ler a construção, e várias pessoas conferiram a aritmética e a consideraram consistente. Aritmética reprodutível e uma prova aceita são coisas diferentes, porém, e a distância entre elas é a história inteira 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 realmente 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 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 precisam fazer.

A pergunta que se discute desde 1999 é simples de enunciar. Se existe um roteamento fracionável barato, 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 mirou. Para entender por que essa distinção importa tanto, precisamos ser precisos.

O teorema vs. a conjectura

Essa é a distinção que a maioria dos textos borra, então serei preciso uma vez e vou me apoiar nela pelo restante do artigo.

Dinitz, Garg e Goemans provaram um resultado sobre congestão: dado um fluxo fracionário válido, você sempre pode convertê-lo em um fluxo 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, conjeturou é 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 sobre congestão está intacto. A conjectura custo+congestão é a peça que Rybin diz ter caído. Se você for levar uma frase daqui, que seja essa. Boa parte da cobertura empolgada troca as duas silenciosamente, e a diferença entre elas é o gap matemático inteiro que levou 30 anos para fechar.

O que o GPT-5.6 realmente construiu

A instância de Rybin é pequena o suficiente para caber em um parágrafo. Uma origem, alguns nós intermediários formando uma “espinha” compartilhada e três terminais, cada um com uma demanda. Cada terminal tem duas rotas para casa: um caminho direto caro ou um desvio gratuito pela espinha compartilhada.

A tensão é estrutural. Os desvios baratos competem por espaço na espinha, então, se muitos terminais tentam trafegar pelo barato ao mesmo tempo, uma estrada da espinha estoura. Se você empurra isso o suficiente, apenas um terminal consegue pegar o caminho barato em qualquer roteamento não fracionável válido. Os demais são forçados aos caminhos diretos caros, e o custo sobe. O fluxo fracionário, livre para dividir, espalha cada demanda pelos dois caminhos e passa por baixo de todas as capacidades ao mesmo tempo. É assim que você obtém um custo fracionário abaixo do menor custo não fracionável legal. Os números de Rybin para sua instância são 58 e 60.

Vou ser honesto sobre um limite aqui. Não consegui reproduzir exatamente o grafo de Rybin — as capacidades específicas e os conflitos par-a-par — a partir de uma fonte primária. A transcrição dele descreve um ponto específico em uma família de parâmetros, e a descrição amplamente compartilhada de “sete nós” é uma abstração disso, não uma construção que eu tenha verificado aresta por aresta. Então não vou montar uma derivação arrumadinha de 58 e fingir que é dele. O que eu posso fazer é te entregar uma instância autocontida que mostra o mesmo mecanismo, pequena o bastante 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 que Rybin compartilhou 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 abanando, afirmando claramente que apresentar o que tinha como um contraexemplo válido seria falso.

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

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

O quarto prompt, segundo relatos algo próximo de “já cansei das suas falhas, finalize 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 o LaTeX completo. A paciência importou. 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 aviso rápido antes do código. O que segue não é o grafo de Rybin. É uma instância esquemática que construí para ser honesta, em que cada terminal realmente tem exatamente duas rotas, a aritmética fecha e o gap é real. Ela mostra o formato de um contraexemplo desse tipo e a técnica de verificação. Sozinha, não refuta nada — e vou explicar por quê logo depois de você rodar.

O setup: três terminais, 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 modo que cada par deles dispute um gargalo próprio: a estrada A é compartilhada pelos terminais 1 e 2, a estrada B pelos terminais 1 e 3, a estrada C pelos terminais 2 e 3. No fluxo fracionário, cada terminal manda 2/5 da sua demanda pelo barato e 3/5 pelo caro, o que custa 30 x 3/5 x 3 = 54. Cada estrada carrega então 4 + 4 = 8 unidades fracionariamente, e o orçamento de congestão é essa carga mais D, ou seja, 18.

Agora veja o que o roteamento não fracionável faz com isso. Dois terminais indo pelo barato despejam 10 + 10 = 20 unidades na estrada que compartilham, acima do orçamento de 18. Então, no máximo um terminal pode seguir pelo 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 um custo fracionário de 54, um custo mínimo não fracionável legal de 60 e um gap 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 terminal 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 terminal realmente tiver duas rotas e nada mais. Construa esse grafo com estradas e nós reais e tende a aparecer uma quarta rota barata a partir da combinatória. Um terminal encontra um terceiro caminho barato para casa que fica dentro do orçamento, e o gap some. Essa rota extra é exatamente a falha que o modelo relatou nas três primeiras tentativas. Um gadget limpo e simétrico que quebra 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. Determinar se um grafo específico realmente tem essa propriedade, sem vazamentos, é a parte difícil — e é por isso que a instância real de Rybin é um ponto ajustado em uma família de parâmetros, e não um triângulo arrumado.

O que ainda está em aberto

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.

Não encontrei o grafo exato publicado reconstruído de forma independente a partir de uma fonte primária. Os números em circulação vêm do post dele e da transcrição compartilhada. Vários pesquisadores conferiram a aritmética e a consideraram consistente, e um mostrou que a instância dele se encaixa em 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 árbitro. Trate o 58 vs. 60 como uma alegação bem sustentada, não como um fato estabelecido.

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 relatada como derrubada com ajuda de IA em cerca de três meses, e vale observar o padrão.

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

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