GPT-5.6 y la conjetura de Dinitz-Garg-Goemans

El 22 de julio de 2026, Dmitry Rybin publicó en X una afirmación que hizo que más de uno dejara el café en la mesa: GPT-5.6 Pro había producido un contraejemplo a la conjetura de Dinitz-Garg-Goemans, abierta en optimización combinatoria desde hace unos 30 años. La prueba de concepto era un grafo pequeñísimo. Coste de flujo fraccionario 58, coste de flujo no divisible 60. Dos puntos, tres décadas, cuatro prompts.

La mayoría de coberturas repiten los números sin mostrar el mecanismo que los produce, y es justo ahí donde está la lección. También es donde tengo que ser claro contigo sobre qué se ha verificado y qué no. Versión corta: los conceptos son sólidos, la noticia es una afirmación y no aún un teorema, y si te sientas a reproducir el grafo exacto desde cero, entenderás por qué estos problemas son difíciles en cuanto tu reconstrucción empiece a hacer agua.

La respuesta rápida

Rybin cuenta que GPT-5.6 Pro, guiado por cuatro prompts de menos de 60 palabras en total, produjo un supuesto contraejemplo a la conjetura de coste de Goemans, un problema abierto desde aproximadamente 1999. Su instancia es un grafo dirigido pequeño con una única fuente y tres terminales de entrega. Afirma que el enrutamiento divisible (fraccionario) cuesta 58, mientras que cualquier enrutamiento no divisible que mantenga la congestión dentro del presupuesto permitido cuesta al menos 60. Esa diferencia de dos puntos, si supera la revisión formal, basta para hundir la conjetura.

No ha pasado por revisión por pares. Rybin publicó toda la conversación con ChatGPT para que cualquiera pueda leer la construcción, y varias personas han comprobado su aritmética y la han encontrado consistente. Aun así, aritmética reproducible y una demostración aceptada son cosas distintas, y la distancia entre ambas es la historia completa de este artículo.

¿Qué es la conjetura de Dinitz-Garg-Goemans?

Antes de valorar qué cayó —o pudo haber caído—, hay que entender qué dice realmente la conjetura.

Imagina un almacén que envía pedidos a tres pueblos por una red de carreteras. Si puedes dividir un envío, puedes mandar medio pedido por una carretera y medio por otra. Eso es enrutamiento fraccionario, y es flexible; suele encontrar un conjunto de rutas más barato. Pero muchos envíos reales no se pueden dividir. Un pedido, un camión, una carretera, de principio a fin. Eso es flujo no divisible, y es lo que en la práctica hace un pedido de carga, un paquete de red o un contenedor.

La pregunta que se viene masticando desde 1999 es fácil de formular. Si existe un enrutamiento fraccionario barato, ¿puedes encontrar siempre un enrutamiento no divisible que también sea barato sin sobrecargar en exceso las carreteras?

Yefim Dinitz, Naveen Garg y Michel Goemans resolvieron la mitad del problema. La otra mitad es la que atacó GPT-5.6. Para entender por qué esa distinción importa tanto, tenemos que ser precisos.

El teorema vs. la conjetura

Esta es la distinción que más artículos difuminan, así que seré preciso una vez y me apoyaré en ello para el resto del texto.

Dinitz, Garg y Goemans demostraron un resultado sobre congestión: dado un flujo fraccionario válido, siempre puedes convertirlo en uno no divisible sin superar la capacidad de ninguna carretera en más que la mayor de las demandas; llamemos D a ese valor. Ese teorema no está en cuestión y nunca lo estuvo.

Lo que Goemans conjeturó por separado es una versión más fuerte, sensible al coste: que la misma conversión podría mantener a la vez bajo el coste total y la congestión. Congestión y coste, ambos acotados, en un único enrutamiento. El teorema de solo congestión está a salvo. La conjetura de coste más congestión es la pieza que, según Rybin, cayó. Si tienes que quedarte con una frase de este artículo, que sea esa. Mucha de la cobertura entusiasmada intercambia ambas cosas en silencio, y la diferencia entre ellas es la brecha matemática que ha llevado 30 años cerrar.

Qué construyó realmente GPT-5.6

La instancia de Rybin es lo bastante pequeña como para describirla en un párrafo. Una fuente, algunos nodos intermedios que forman una "columna vertebral" compartida y tres terminales, cada uno con una demanda. Cada terminal tiene dos caminos a casa: una ruta directa cara o un desvío gratuito por la columna compartida.

La tensión es estructural. Los desvíos baratos compiten por espacio en la columna, así que si demasiados terminales intentan ir por lo barato a la vez, alguna carretera de la columna se satura. Si empujas lo suficiente, solo un terminal puede tomar su ruta barata en cualquier enrutamiento no divisible válido. El resto se ve forzado a sus rutas directas caras y el coste sube. El flujo fraccionario, libre para dividir, reparte cada demanda entre ambos caminos y se cuela por debajo de todas las capacidades a la vez. Así se obtiene un coste fraccionario inferior al coste del mejor no divisible legal. Las cifras de Rybin para su instancia son 58 y 60.

Voy a ser honesto con una limitación. No he podido reproducir el grafo exacto de Rybin, las capacidades concretas y los conflictos por pares, a partir de una fuente primaria. Su transcripción describe un punto particular dentro de una familia de parámetros, y la famosa descripción de "siete nodos" es una abstracción de ello, no una construcción que yo haya verificado arista por arista. Así que no voy a escenificar una derivación pulcra del 58 y fingir que es suya. Lo que sí puedo hacer es darte una instancia autocontenida que muestra el mismo mecanismo, lo bastante pequeña como para comprobarla por fuerza bruta, para que veas con tus propios ojos cómo "lo fraccionario gana a cualquier no divisible legal". 

Cuatro prompts, varias horas

El recuento de prompts es lo menos interesante de esta historia, aunque fue la parte que se volvió viral.

El chat que compartió Rybin muestra al modelo fallando primero, y fallando con precisión. El prompt inicial le pedía hallar un contraejemplo estructurado. Trabajó durante buena parte de una hora y volvió con las manos vacías, afirmando abiertamente que presentar lo que tenía como un contraejemplo válido sería falso.

Al decirle que siguiera, volvió a ejecutar y volvió a reportar nada, describiendo cómo cada construcción prometedora acababa revelando una ruta adicional oculta que destruía la separación coste-congestión una vez enumerados todos los caminos. Un tercer prompt pidiendo una estrategia más limpia acotó el marco y aun así no dio un resultado terminado.

Eso no es "cuatro prompts y listo". Son horas de un modelo chocando contra muros y diciendo la verdad sobre ellos. El muro concreto con el que tropezaba —aparece una ruta extra y arruina la separación— es exactamente lo que la construcción final evitó, fijando cada terminal a justo dos caminos para que todo el espacio de enrutamientos sean ocho opciones que puedes enumerar a mano. Ten presente ese modo de fallo. Estás a punto de encontrártelo tú también.

El cuarto prompt, según se cuenta algo cercano a "ya basta de fallar, termina con un contraejemplo completo e incondicional", fue el que produjo la construcción funcional, junto con certificados de prueba, un programa de enumeración y LaTeX completo. La paciencia importó. También las negativas anteriores: fueron autoevaluaciones honestas.

Compruébalo tú mismo

Aquí es donde la cobertura de DataCamp puede hacer algo que una noticia no puede: dejarte ejecutar la verificación.

Un aviso rápido antes del código. Lo que sigue no es el grafo de Rybin. Es una instancia esquemática que construí con honestidad, en la que cada terminal tiene exactamente dos rutas, la aritmética cierra y la brecha es real. Te muestra la forma de un contraejemplo así y la técnica para comprobarlo. Por sí sola no refuta nada, y explicaré por qué justo después de que lo ejecutes.

El planteamiento: tres terminales, cada uno enviando 10 unidades, así que la mayor demanda D es 10. Cada uno tiene un camino directo caro (coste 30) y un camino barato gratis. Los caminos baratos se disponen de forma que cada par de ellos compite por su propia carretera cuello de botella privada: la carretera A la comparten los terminales 1 y 2, la B los terminales 1 y 3, y la C los terminales 2 y 3. En el flujo fraccionario, cada terminal envía 2/5 de su demanda por lo barato y 3/5 por lo caro, lo que cuesta 30 x 3/5 x 3 = 54. Cada carretera soporta entonces 4 + 4 = 8 unidades fraccionarias, y el presupuesto de congestión es esa carga más D, es decir, 18.

Ahora mira qué hace el enrutamiento no divisible con eso. Dos terminales yendo ambos por lo barato cargan 10 + 10 = 20 unidades en su carretera compartida, superando el presupuesto de 18. Así que como mucho un terminal puede ir por lo barato; los otros dos pagan 30 cada uno. Coste mínimo legal no divisible: 60. Frente a un fraccionario de 54. Hay ocho enrutamientos posibles, así que los comprobamos 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)")

Si lo ejecutas, obtendrás un coste fraccionario de 54, un coste mínimo legal no divisible de 60 y una brecha de 6. Las tres filas sobrecargadas son los tres conflictos por pares; los únicos enrutamientos que sobreviven mantienen como mucho un terminal por lo barato.

¿Entonces la conjetura está muerta? No exactamente, y aquí viene lo que prometí explicar. Esa enumeración de ocho filas solo dice la verdad si cada terminal tiene realmente dos rutas y no más. Si construyes este grafo con carreteras y nodos reales, tiende a aparecer una cuarta ruta barata fruto de la combinatoria. Un terminal encuentra un tercer camino a casa que es barato y se mantiene dentro del presupuesto, y la brecha se cierra. Esa ruta extra es el mismo fallo que el modelo reportó en sus tres primeros intentos. Un artilugio limpio y simétrico que rompa una conjetura de 30 años en ocho líneas de Python sería demasiado bonito para ser verdad, y lo es. El código anterior demuestra que la verificación es sólida y que la propiedad objetivo es real. Determinar si un grafo concreto tiene esa propiedad, sin fugas, es la parte difícil, y por eso la instancia real de Rybin es un punto ajustado dentro de una familia de parámetros y no un triángulo aseado.

Qué sigue sin resolverse

No ha aparecido ningún artículo formal. Rybin compartió la conversación y la construcción; ninguna ha pasado por el proceso de revisión que permitiría a la comunidad matemática cerrar oficialmente la conjetura.

No he encontrado que el grafo publicado se haya reconstruido de forma independiente a partir de una fuente primaria. Las cifras que circulan provienen de su publicación y de la transcripción compartida. Varios investigadores han comprobado su aritmética y la han declarado consistente, y uno mostró que su instancia se inscribe en una familia infinita de tres parámetros sobre los mismos nodos, lo que haría el resultado más rico que una coincidencia afortunada. Es alentador, pero es verificación informal de la comunidad, no un informe de revisores. Trata el 58 vs. 60 como una afirmación bien sustentada, no como un hecho cerrado.

El teorema de congestión de 1999 no se ve afectado por nada de esto.

Parte de un patrón

Esta historia no es un caso aislado. Es la tercera conjetura que, según se informa, cae con ayuda de la IA en unos tres meses, y merece la pena fijarse en el patrón.

El 20 de julio, Claude Fable 5 supuestamente ayudó al matemático Levent Alpöge a encontrar un contraejemplo a la conjetura jacobiana, un problema de 87 años. Antes, en mayo, se dijo que un modelo de OpenAI había refutado la conjetura de distancias unitarias de Erdős, con 80 años de antigüedad. La misma semana de esta noticia, un doctorando de Columbia usó GPT-5.6 con un flujo de trabajo estructurado de Codex para resolver seis problemas abiertos de Erdős en cinco días. La idea común, como dijo un investigador, es que estos sistemas son mejores refutando que demostrando. Un contraejemplo es un único testigo que puedes comprobar; una prueba tiene que cubrir todos los casos. Esa asimetría parece decidir qué problemas caen primero.

La conclusión práctica no es "la IA resuelve las matemáticas". Lo que estamos viendo es a la IA trabajando como una compañera paciente de búsqueda combinatoria exhaustiva: capaz de enumerar familias de parámetros, mantener modos de fallo en memoria de trabajo a lo largo de intentos y decir la verdad cuando una construcción no cierra. Es una capacidad concreta y útil. Y si quieres entender dónde es probable que golpee a continuación, la pregunta no es qué conjeturas son más antiguas, sino cuáles se pueden romper con un único testigo verificable.