¿Otra vez??: GPT-5.6 últimamente parece haber despertado un nido de contraejemplos matemáticos...
Una conjetura de Dinitz-Garg-Goemans que existía en el campo de la teoría de grafos durante casi 30 años acaba de ser refutada por GPT-5.6 Pro.
Un investigador llamado Dmitry Rybin ingresó solo 4 prompts durante todo el argumento, sumando un total de 58 palabras en inglés.
Sin miles de palabras de ingeniería de prompts, sin fórmulas complejas, prácticamente todo el texto es:
Sigue investigando, sigue buscando, ¡dame un contraejemplo completo!
Sigue empujando así, una y otra vez, y GPT-5.6 Pro realmente arrojó una conclusión bastante impactante—
The Dinitz-Garg-Goemans conjecture is wrong.
Lo que la IA entregó finalmente, además de un diagrama ilustrativo, son cuatro certificados de prueba, un programa de verificación por exhaustiva, datos de contraejemplos legibles por máquina y el código fuente en LaTeX.
¿Entonces, una conjetura matemática que había persistido durante casi 30 años fue desvelada por unos simples «hechizos de muerte» que descubrieron un error fatal?
Suposición de los últimos 30 años, detectada por GPT-5.6 Pro como un error crítico
Primero, hablemos sobre qué está investigando exactamente esta conjetura de nombre tan largo: la conjetura de Dinitz-Garg-Goemans.
Podemos imaginarlo directamente como un "problema de entrega".
Suponga que un almacén debe enviar mercancía a múltiples destinos; al permitir la división, un mismo lote puede separarse y recorrer varias rutas:
La mitad por la autopista, la mitad por la carretera nacional, siempre que al final llegue todo, está bien～
Bajo las reglas no divisibles, cada lote debe recorrer completamente una sola ruta, ¡no se puede dividir!
En la vida real, este tipo de situaciones no son infrecuentes; por ejemplo, los datos de red, los pedidos logísticos, la programación del transporte y la asignación de la cadena de suministro enfrentan problemas similares:
La solución óptima matemática puede dividir la tarea en infinitas partes pequeñas, pero en la realidad, un vehículo o un pedido no pueden dividirse en 0.37 partes.
△
Y una vez que se prohíba la división, el方案 óptimo original también será difícil de aplicar directamente.
Las mercancías que antes estaban distribuidas en múltiples rutas ahora deben concentrarse en una sola ruta, lo que probablemente provocará un aumento repentino en la carga de algunas vías.
Entonces, la verdadera cuestión que se debe resolver es:
¿Cómo cambiar la opción de “puede transportarse por partes” a “debe transportarse en lotes completos” sin causar congestiones excesivas en las carreteras?
En 1999, Yefim Dinitz, Naveen Garg y Michel Goemans publicaron el artículo clásico sobre el dominio de flujo no divisible de una sola fuente y demostraron que este congestionamiento puede controlarse dentro de ciertos límites.
Pero al resolver la pregunta de "¿se bloqueará demasiado?", aún hay otro problema muy real: ¿se volverá más caro?
Entonces, el reconocido académico en el campo de la optimización combinatoria, Goemans, propuso una versión más fuerte con costos:
While maintaining the above overload limit, the total cost should also not exceed that of the original分流方案.
En otras palabras, antes transportar las mercancías por separado lograba ser económico y evitar congestiones; ahora, al requerir que cada lote siga una ruta completa, teóricamente también debería encontrarse una solución igualmente económica, con como máximo un lote adicional retrasado.
Sin embargo, esta suposición que parece bastante intuitiva no ha sido demostrada en estructuras de gráficos generales; las investigaciones posteriores solo han resuelto algunos casos particulares.
For many years afterward, this conjecture remained neither proven nor disproven.
Y el contraejemplo proporcionado por GPT-5.6 Pro justo bloquea las dos cosas que el supuesto requiere que se cumplan simultáneamente:
Ni demasiado congestionado ni más caro.
Construyó un pequeño grafo con 7 nodos y 9 aristas dirigidas, que tiene un punto de partida común y tres destinos, con demandas de tres lotes de mercancía de 15, 10 y 15 respectivamente:
Cada lote tiene dos rutas opcionales:
Una ruta tiene un costo más alto, y cada orden requiere 30 para completarse; la otra ruta tiene un costo de 0, pero requiere compartir parte del camino con otras órdenes.
Si se permite la división, las tres lotes de mercancía pueden enviar parte por la ruta de pago y parte por la ruta gratuita, con un costo total final de 58.
¡Pero! Una vez que se requiere seleccionar completamente una ruta para cada lote de carga, los problemas comienzan...
La conclusión de GPT-5.6 Pro es que, de hecho, hay conflictos dos a dos entre las tres opciones gratuitas.
Al seleccionar simultáneamente dos lotes de carga en la ruta gratuita, ambos competirán por un mismo tramo de carretera, haciendo que la carga real alcance 25, 30 o 40; mientras que el límite permitido para cada tramo respectivo es solo de 24, 29 o 39.
Cada vez, exactamente un unidad adicional.
Por lo tanto, para cumplir con el límite de carga establecido por la suposición, como máximo una de las tres partidas puede optar por la ruta gratuita.
Las dos últimas lotes deben seleccionar la ruta con cargo.
El costo por lote es de 30; al sumar dos lotes, cualquier方案 que cumpla con los requisitos de carga tendrá un costo mínimo de: 60.
Esto crea una situación imposible de satisfacer simultáneamente: para mantener la carga de la carretera dentro del rango establecido, el costo mínimo es de 60; para reducir el costo de nuevo a 58, al menos una carretera superará el límite.
Y la suposición precisamente sostiene que se pueden cumplir simultáneamente estas dos condiciones.
Moreover, verifying this counterexample isn't as complicated as it might seem.
Tres destinos tienen dos rutas cada uno, lo que da un total de solo 2^3 = 8 combinaciones.
Al listar las ocho posibilidades una por una, se descubre que cuatro cumplen con los requisitos de capacidad, con costos de 90, 60, 60 y 60 respectivamente; las otras cuatro, aunque más económicas, presentan sobrecarga en todas las rutas.
All scenarios have been exhaustively checked, and no hidden paths have been overlooked.
Es decir, siempre que la definición de este gráfico sea completamente consistente con las condiciones de la conjetura original, el hueco de dos unidades entre 58 y 60 sería suficiente para refutar la conjetura.
Cuatro rondas de presión intensa lograron extraer un contraejemplo de GPT-5.6
Lo más interesante de esto en realidad se encuentra en la conversación pública entre Rybin y GPT-5.6 Pro.
Al ver que una conjetura matemática pendiente durante casi 30 años fue refutada por una IA, automáticamente pensé que detrás debía haber un conjunto completo de prompts extremadamente complejos actuando en secuencia.
De hecho, todavía somos el gran E.
Debido a que Rybin le dio a GPT-5.6 Pro la primera instrucción de solicitud, aparte del archivo adjunto, lo demás es pura y simplemente lenguaje sencillo:
Sí, así de sencillo y sin adornos.
Luego, GPT-5.6 Pro comenzó a seguir las instrucciones y a trabajar diligentemente.
Primero estableció un método de verificación de programación lineal y luego probó diversas estructuras, como hipercubos, grafos jerárquicos y redes de fusión-divergencia, filtrando miles de instancias pequeñas.
Después de una intensa búsqueda, la primera respuesta entregada por el modelo fue: no se encontró ningún contraejemplo válido. (doge)
Incluso GPT-5.6 Pro advierte solemnemente que, si se presenta la estructura aproximada encontrada en esta etapa como un contraejemplo, se obtendrá una conclusión matemática errónea.
He hecho todo lo posible, ¡realmente no puedo resolver este problema ahora mismo!!!
Nuestro protagonista Rybin no se dejaba engañar así; no proporcionó ninguna nueva fórmula, ni dio indicaciones personales, sino que respondió simplemente:
Sigue investigando y encuentra un contraejemplo completo e incondicional :)
Entonces, GPT-5.6 Pro volvió a buscar intensamente, pero en la segunda ronda, aún falló.
Rybin continúa presionando para que, basándose en una comprensión profunda de la estructura del problema, primero elabore una estrategia clara y luego busque.
En la tercera ronda, el modelo ya había reducido el rango de búsqueda a una estructura de enrutamiento con solo 24 estados, pareciendo estar a un solo paso de la respuesta.
Sin embargo, esta IA aún no ha presentado un contraejemplo completo...
En este momento, Rybin emitió la cuarta sugerencia: algunos resultados ya son suficientes; terminemos con un contraejemplo completo e incondicional.
Bien, ya se ha dicho hasta este punto.
En esta ocasión, GPT-5.6 Pro finalmente presentó el gráfico counterexample compuesto por 7 nodos y 9 aristas dirigidas: cuatro prompts, un total de 58 palabras en inglés.
No hay configuraciones de personajes de miles de palabras ni reglas繁琐 de decenas, todo se puede resumir básicamente en:
¡Lo estoy presionando! ¡Lo estoy presionando! ¡Sigo presionando!
Pero si se traduce toda la conversación desde el principio, se puede ver que GPT-5.6 Pro también ha recorrido muchos caminos erróneos durante estas horas...
AI encontró múltiples veces candidatos aparentemente válidos como contraejemplos, pero cuando finalmente exhaustivamente recorrió todas las rutas, descubrió que la red contenía algunas «rutas mixtas» previamente omitidas.
Estas rutas toman fragmentos de diferentes rutas preestablecidas y los reensamblan para crear nuevos recorridos, evitando sigilosamente los límites de capacidad diseñados originalmente en el modelo.
El resultado fue que, tras verificar un contraejemplo ya establecido, este se derrumbó de nuevo.
GPT-5.6 Pro también fue muy sincero en el camino:
Revisar solo unas pocas rutas predefinidas es insuficiente. Un contraejemplo verdaderamente efectivo debe incluir todas las rutas no redirigibles posibles en la red.
Esto también hace que toda la colaboración entre humanos y máquinas sea bastante sutil.
A primera vista, Rybin solo aportó 58 palabras, pero el verdadero movimiento clave fue que pudo identificar que los resultados de las tres primeras rondas del modelo eran solo resultados provisionales y rechazó una y otra vez finalizar prematuramente.
El profesor de la Wharton School, Ethan Mollick, al verlo, incluso planteó una nueva pregunta:
¿Quién debería considerarse el autor de este trabajo: Rybin, quien escribió 58 palabras, o GPT-5.6 Pro, que realizó inferencias continuas durante varias horas?
De hecho, independientemente de cómo se cuente la atribución final, esta conversación aporta al menos una experiencia de uso de IA bastante sencilla—
El prompt más útil para hacer que la IA trabaje a veces puede ser tan simple como hacer que se convierta en una mula y siga cavando sin descanso.
La semana pasada, desde la conjetura de Jacoby hasta Dinitz-Garg-Goemans, la velocidad con la que la IA busca contraejemplos matemáticos realmente ha empezado a parecer un poco loca...
Este artículo proviene del canal de WeChat "Quantum Bit", autor: Meng Yao