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é encima de 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ño. Coste de flujo fraccionario 58, coste de flujo no divisible 60. Dos puntos, tres décadas, cuatro prompts.

La mayoría de las coberturas repiten los números sin mostrar el mecanismo que hay detrás, y es justo ahí donde está la lección. También es donde tengo que ser claro contigo sobre lo que se ha verificado y lo que no. Versión corta: los conceptos son sólidos, la noticia es una afirmación y aún no un teorema, y si te pones a reproducir el grafo exacto desde cero, entenderás por qué problemas como este son duros en el mismo momento en que tu reconstrucción hace agua por algún sitio.

La respuesta rápida

Rybin cuenta que GPT-5.6 Pro, dirigido con cuatro prompts que no llegan a 60 palabras en total, produjo un supuesto contraejemplo a la conjetura de costes 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 brecha de dos puntos, si supera la revisión formal, basta para tumbar la conjetura.

No ha pasado por revisión por pares. Rybin publicó la conversación completa de 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 prueba aceptada son cosas distintas, y la distancia entre ambas es toda la historia de este artículo.

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

Antes de valorar lo que cayó, o pudo caer, tenemos que entender qué dice realmente la conjetura.

Imagina un almacén que envía pedidos a tres ciudades por una red de carreteras. Si puedes dividir un envío, puedes mandar la mitad por una carretera y la otra mitad por otra. Eso es enrutamiento fraccionario, y es flexible; suele encontrar un conjunto de rutas más baratas. Pero mucho transporte real no se puede dividir. Un pedido, un camión, una carretera, de principio a fin. Eso es flujo no divisible, y es lo que un pedido de mercancía, un paquete de red o un contenedor tiene que hacer en la práctica.

La pregunta que se viene masticando desde 1999 es fácil de enunciar. Si existe un enrutamiento fraccionario barato, ¿siempre puedes encontrar un enrutamiento no divisible que sea también barato sin sobrecargar demasiado 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 muchísimo, 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 demanda individual; llamemos D a ese número. Ese teorema no está en cuestión y nunca lo estuvo.

Lo que Goemans planteó por separado como conjetura es la versión más fuerte y consciente del coste: que esa misma conversión podría mantener bajo el coste total a la vez que mantiene baja la congestión. Congestión y coste, ambos acotados, en un único enrutamiento. El teorema sólo de congestión está a salvo. La conjetura de coste más congestión es la pieza que, según Rybin, ha caído. Si te quedas con una sola frase de este texto, que sea esa. Mucha cobertura entusiasta intercambia sutilmente ambos resultados, y la diferencia entre ellos es justo el hueco matemático que ha tardado 30 años en cerrarse.

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 formando 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 a través de la columna compartida.

La tensión es estructural. Los desvíos baratos compiten por espacio en la columna, de modo que si demasiados terminales intentan ir por la barata a la vez, alguna carretera de la columna se desborda. Si fuerzas lo suficiente, en cualquier enrutamiento no divisible válido sólo uno de los terminales puede tomar su camino barato. El resto se ve obligado 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 cada capacidad a la vez. Así es como obtienes un coste fraccionario por debajo del coste no divisible legal más barato. Las cifras de Rybin para su instancia son 58 y 60.

Voy a ser sincero con un límite aquí. 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 concreto dentro de una familia de parámetros, y la conocida descripción de "siete nodos" es una abstracción de ello, no una construcción que yo haya verificado arista a arista. Así que no voy a montar una derivación pulcra del 58 y fingir que es la suya. Lo que sí puedo hacer es darte una instancia autocontenida que muestra el mismo mecanismo, lo bastante pequeña para comprobarla por fuerza bruta, para que veas con tus propios ojos qué significa "el fraccionario supera a cualquier no divisible legal". 

Cuatro prompts, varias horas

El número de prompts es lo menos interesante de esta historia, aunque es la parte que se hizo viral.

El registro del chat que compartió Rybin muestra que el modelo primero falló, y falló con precisión. El prompt de apertura le pedía encontrar un contraejemplo estructurado. Trabajó durante buena parte de una hora y volvió con las manos vacías, afirmando directamente que presentar lo que tenía como contraejemplo válido sería falso.

Al decirle que siguiera, volvió a ejecutar y, de nuevo, no reportó nada, describiendo cómo cada construcción prometedora acababa revelando una ruta extra oculta que destruía la separación coste-congestión una vez se enumeraban todos los caminos. Un tercer prompt pidiendo una estrategia más limpia compró un marco más estrecho y aun así sin resultado final.

Eso no es "cuatro prompts y listo". Son horas de un modelo chocando contra muros y diciéndote la verdad sobre ellos. El muro concreto contra el que chocaba, aparece una ruta extra y arruina la separación, es exactamente lo que la construcción final se diseñó para evitar, fijando cada terminal a exactamente 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 toparte con él tú también.

El cuarto prompt, por lo visto algo cercano a "ya basta de fallar, por favor termina con un contraejemplo completo e incondicional", es el que produjo la construcción que funciona, junto con certificados de prueba, un programa de enumeración y el 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 un post de noticias 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í para ser honesta, una en la que cada terminal tiene de verdad 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 ahora te explicaré por qué justo después de que lo ejecutes.

El planteamiento: tres terminales, cada uno con 10 unidades, así que la mayor demanda D es 10. Cada uno tiene una ruta directa cara (coste 30) y una ruta barata gratuita. Las rutas baratas se organizan de forma que cada par de ellas compite por su propia carretera cuello de botella: la carretera A la comparten los terminales 1 y 2, la B los 1 y 3, la C los 2 y 3. En el flujo fraccionario, cada terminal envía 2/5 de su demanda por la barata y 3/5 por la cara, lo que cuesta 30 x 3/5 x 3 = 54. Cada carretera carga entonces 4 + 4 = 8 unidades de forma fraccionaria, y el presupuesto de congestión es esa carga más D, o sea, 18.

Ahora mira qué hace el enrutamiento no divisible con eso. Dos terminales yendo ambos por la barata vierten 10 + 10 = 20 unidades en su carretera compartida, por encima del presupuesto de 18. Así que como mucho un terminal puede ir por la barata; los otros dos pagan 30 cada uno. Coste mínimo legal no divisible: 60. Frente a un fraccionario de 54. Existen ocho enrutamientos, 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, obtienes 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 la barata.

¿Entonces la conjetura está muerta? No exactamente, y esta es la parte que prometí explicar. Esa enumeración de ocho filas sólo dice la verdad si cada terminal de verdad tiene dos rutas y no más. Si construyes este grafo con carreteras y nodos reales, suele aparecer una cuarta ruta barata fruto de la combinatoria. Un terminal encuentra una tercera forma de volver a casa que es barata y se mantiene dentro del presupuesto, y la brecha se cierra. Esa ruta extra es justo el 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 así es. El código anterior demuestra que la comprobación es sólida y que la propiedad objetivo es real. Si un grafo concreto tiene realmente esa propiedad, sin fugas, es la parte difícil, y por eso la instancia real de Rybin es un punto ajustado en una familia de parámetros y no un triángulo aseado.

Lo que sigue sin resolverse

No ha aparecido un 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. Los números que circulan vienen de su post y de la transcripción compartida. Varios investigadores han comprobado su aritmética y la han considerado 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 comprobació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 zanjado.

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 dato aislado. Es la tercera conjetura que, según se informa, cae con ayuda de 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 de Jacobiano, 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 a sus espaldas. 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 apuntó un investigador, es que estos sistemas son mejores refutando que probando. 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 trabajar como un socio de búsqueda paciente y exhaustivo en combinatoria: 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 pueden romperse con un testigo único y comprobable.