OpenAI anunció el 26 de octubre de 2026 que su sistema había producido un resultado que, según la empresa, refutaría la Exponential Time Hypothesis (ETH), una conjetura sobre la complejidad de la satisfacibilidad booleana. OpenAI sitúa el resultado en lenguaje natural el 16 de octubre y su formalización en Lean el 17.
La documentación de Lean concreta qué teorema se formalizó: un algoritmo determinista que cuenta exactamente las asignaciones que satisfacen fórmulas k-CNF canónicas, con k fijo y k ≥ 2. La página distingue esa cota de otras más ajustadas que atribuye al manuscrito. No son la misma afirmación matemática.
Qué formaliza la documentación de Lean
Una fórmula k-CNF reúne cláusulas booleanas, y contar sus asignaciones satisfactorias significa calcular cuántas combinaciones de valores hacen verdadera toda la fórmula. En la página oficial de alcance de Lean, el tiempo de ejecución indicado para el algoritmo es (L+1)^{O_k(1)} 2^{O_k(n(log log n)^2/√log n)}. Aquí, L es la longitud en bits de la codificación y n el número de variables; el subíndice k señala que las constantes pueden depender de k.
La misma página indica que la máquina visita como máximo (L+1)^{O_k(1)} celdas de cinta en total. Es una medida de espacio distinta de la cota de tiempo. La afirmación cubre el conteo exacto para esa clase de fórmulas, con k fijo; no describe una medición de velocidad en ordenadores corrientes.
La cota atribuida al manuscrito es distinta
La página de alcance atribuye al manuscrito fechado el 25 de octubre una cota de tiempo más ajustada: (n+m)^{O_k(1)} 2^{O_k(n log log n/√log n)}, donde m es el número de cláusulas. Para fórmulas con m ≤ Dn, con D > 0 fijo, atribuye además la expresión (n+m)^{O_{k,D}(1)} 2^{O_{k,D}(n/√log n)}.
Estas cotas pertenecen a la exposición del manuscrito según la página de alcance; la documentación presenta por separado el límite del teorema formalizado en Lean. La diferencia importa porque la cota más ajustada no debe atribuirse al enunciado formalizado como si fuera la misma expresión.
Qué implica para ETH y para el software
ETH se refiere a la dificultad de resolver problemas de satisfacibilidad en el peor caso. OpenAI no anunció una solución a P = NP: la afirmación que presentó se refiere a ETH. Y una cota asintótica subexponencial, cuyo exponente crece más despacio que n, no equivale por sí sola a que los solucionadores SAT actuales vayan a funcionar más rápido. OpenAI dijo que convertir avances teóricos en mejoras prácticas requeriría mucha más investigación.
El vídeo de Adem B10 ofrece una explicación visual de ETH y de las cotas asintóticas. Está en inglés y utiliza un rompecabezas de interruptores como ejemplo simplificado, no como representación del algoritmo de OpenAI.
La revisión externa anunciada
OpenAI anunció el 26 de octubre un grupo externo dirigido por Russell Impagliazzo, Ramamohan Paturi y Ryan Williams para examinar y explicar el resultado. En una actualización del 28 de octubre de 2026, ExplainX informó que no se había comunicado una confirmación independiente hasta ese día.
