Donald Knuth publica un artículo sobre cómo Claude Opus 4.6 resolvió un problema abierto de combinatoria
(www-cs-faculty.stanford.edu)Resumen clave
- Donald Knuth, científico de la computación y autor de 'The Art of Computer Programming (TAOCP)', anunció que el más reciente modelo de IA, 'Claude Opus 4.6', resolvió un problema abierto de combinatoria en el que él había estado trabajando durante varias semanas.
- En el problema de encontrar una descomposición en ciclos hamiltonianos de un grafo dirigido, Claude descubrió una estructura algorítmica generalizada que funciona mediante 31 ejecuciones de scripts de Python y su propio bucle de retroalimentación.
- Knuth, que en el pasado había sido escéptico y había señalado las limitaciones de la IA generativa, evaluó este resultado como un "avance dramático en la deducción automática y la resolución creativa de problemas", sugiriendo que revisará su postura previa sobre la IA.
Análisis en profundidad
El problema resuelto: descomposición en ciclos hamiltonianos (Hamiltonian Cycle Decomposition)
Knuth estaba estudiando un problema de descomposición en ciertos grafos dirigidos (digraphs) mientras escribía el próximo volumen de TAOCP. En un grafo con $m^3$ vértices $ijk$, donde $0 \le i, j, k < m$, cada vértice tiene 3 arcos dirigidos a $i+jk$, $ij+k$, $ijk+$ (donde $i+ = (i+1) \bmod m$). El objetivo era encontrar una solución general (general decomposition) que descompusiera estos arcos en 3 ciclos dirigidos de longitud $m^3$ para todos los casos con $m > 2$. Knuth había resuelto el caso $m=3$, pero estaba teniendo dificultades para derivar una fórmula general para valores mayores.
Principio de implementación y contexto técnico: razonamiento híbrido y bucle autónomo de exploración
Filip Stappers, colega de Knuth, introdujo este problema en 'Claude Opus 4.6', el más reciente modelo híbrido de razonamiento de Anthropic. Para ello, además de la consulta en sí, le impuso mediante el prompt fuertes restricciones que forzaban un flujo de trabajo agentic.
Claude reformuló de inmediato el problema en términos matemáticos y escribió scripts de Python (exploreXX.py) para iniciar un bucle de validación de hipótesis. Durante aproximadamente una hora, realizó 31 exploraciones probando diversos algoritmos, entre ellos brute force, fiber decompositions y simulated annealing.
El punto de inflexión clave en la resolución
En particular, en la exploración número 25, Claude analizó sus propias limitaciones y cambió la dirección de la búsqueda al concluir que "el algoritmo de simulated annealing puede encontrar soluciones individuales, pero no puede ofrecer una construcción matemática general, por lo que se necesita un enfoque de matemáticas puras". Finalmente, en la exploración número 31, logró derivar una estructura general exacta que funciona cuando $m$ es impar, basándose en los patrones estructurales de exploraciones anteriores. A partir de este resultado, Knuth completó la demostración matemática y la bautizó como 'descomposiciones tipo Claude' (Claude-like decompositions).
Código y datos principales
A continuación se muestran las restricciones clave (prompt) que Filip Stappers le dio a Claude y parte del registro de autoevaluación de Claude.
# 1. Restricciones de flujo de trabajo impuestas a Claude (control de bucle y documentación forzada)
"""
After EVERY exploreXX.py run, IMMEDIATELY update this file [plan.md] before doing anything else.
No exceptions. Do not start the next exploration until the previous one is documented here.
"""
# 2. Reformulación matemática del problema por parte de Claude (enfoque inicial)
"""
Need sigma: Z3 m — S3, assigning a permutation of {0,1,2} at each vertex;
cycle c at vertex v goes in direction sigma(v)[c].
Each resulting functional digraph must be a single Hamiltonian cycle.
"""
# 3. Autoevaluación de Claude después de la exploración 25 (cambio de rumbo)
"""
SA(Simulated Annealing) can find solutions but cannot give a general construction.
Need pure math.
"""
10 comentarios
La persona que aparece en los libros de texto no deja de seguir agregándoles cosas....
(De acuerdo)
Claro, escribir libros de texto es justamente el papel de esa persona (asiente).
jajajaja ahora seguro le va a agregar todavía más con IA
Entonces sí iba a salir más de TAOCP.
Compartió tal cual el método de usar IA para resolver un problema matemático y encima escribió el paper con el TeX que él mismo creó.... una locura total
Gracias al artículo, conocí TAOCP por primera vez; creo que voy a echarle un vistazo con calma.
Dice que está escribiendo el próximo volumen de TAOCP
Entonces parece que sí van a salir más tomos de la serie jajajajaja
¿Todavía sigue vivo?
Una persona que incluso ahora sigue haciendo correcciones...