sol-feyissa-5Ib2B9MBJhQ-unsplash

Dos sistemas internos de inteligencia artificial de laboratorios rivales —uno de OpenAI y otro de Anthropic— produjeron de manera independiente pruebas de que la Hipótesis del Tiempo Exponencial (ETH, por su sigla en inglés) es falsa. Sus resultados fueron publicados con pocas horas de diferencia el 26 de octubre y ambos sitúan el descubrimiento central el 16 de octubre de 2026. La coincidencia es extraordinaria. Si las pruebas superan el escrutinio independiente, los investigadores podrían verse obligados a revisar más de 800 artículos publicados que utilizaron la ETH como supuesto fundamental.

La Hipótesis del Tiempo Exponencial, propuesta en 1999 por Russell Impagliazzo y Ramamohan Paturi, de la Universidad de California en San Diego, y formalizada posteriormente con Francis Zane en 2001, sostiene que 3-SAT —el problema canónico de satisfacibilidad booleana en el centro de la NP-completitud— no puede resolverse en tiempo subexponencial. En términos sencillos, la hipótesis afirma que la clase más fundamental de problemas lógicos no admite un algoritmo significativamente más rápido que una búsqueda exhaustiva de complejidad exponencial. Durante un cuarto de siglo, investigadores de teoría de grafos, biología computacional, optimización de bases de datos, complejidad parametrizada y criptografía construyeron resultados sobre esa afirmación, utilizando la ETH para descartar clases enteras de algoritmos más rápidos sin tener que resolver por sí misma la cuestión P vs. NP.

Las dos pruebas producidas por IA hacen precisamente lo que la ETH consideraba imposible. Ambas están verificadas en Lean 4: fueron revisadas por un asistente de demostración que certifica paso a paso la consistencia lógica del argumento. Además, las dos están disponibles en GitHub.

La afirmación de OpenAI: tres resultados en diez días

El anuncio de OpenAI del 26 de octubre presentó tres resultados distintos de un modelo interno aún no divulgado. El más importante para la teoría de la complejidad aparece en un artículo titulado "La Hipótesis del Tiempo Exponencial es falsa". Allí se describe un algoritmo determinista —sin componentes aleatorios— que cuenta exactamente las soluciones de una fórmula k-CNF en un tiempo aproximado de 2^(n/(log n)^(1/2+o(1))), utilizando únicamente espacio polinómico. Como contar las asignaciones que satisfacen una fórmula es más difícil que determinar si existe al menos una, un algoritmo capaz de resolver el problema más complejo también resuelve el más sencillo. El caso 3-SAT refuta directamente la ETH.

El modelo, que OpenAI no ha publicado, produjo la refutación en lenguaje natural el 16 de octubre y formalizó el resultado en Lean al día siguiente. El artículo está fechado el 17 de octubre y fue revisado el 25. Tanto el texto como el código en Lean están disponibles en el repositorio de OpenAI en GitHub.

El anuncio de OpenAI también incluyó una prueba de la conjetura del suavizado local —propuesta por Christopher Sogge en 1991— en todas las dimensiones. Debido a la relación entre estas conjeturas, el resultado también resolvería la conjetura de Kakeya y la conjetura de restricción de Stein en todas las dimensiones. Hasta ahora, los matemáticos habían establecido la conjetura de Kakeya únicamente en tres dimensiones, en una prueba publicada por Hong Wang y Joshua Zahl en 2025. Un tercer resultado —una prueba rigurosa de existencia para ciertas teorías cuánticas de campos interactuantes en cuatro dimensiones, incluida la cromodinámica cuántica (QCD) y la teoría pura de Yang-Mills— constituye, según la afirmación, una solución a uno de los siete Problemas del Milenio del Instituto Clay de Matemáticas.

OpenAI dijo en septiembre que no reclamaría el Premio del Milenio por su resultado anterior sobre las ecuaciones de Navier-Stokes, y adoptó la misma posición en este caso: el reconocimiento académico por resultados producidos con IA debe corresponder a los investigadores que expliquen y verifiquen el trabajo, no a OpenAI.

Los autores de la ETH examinarán ahora la afirmación

La estructura de revisión organizada por OpenAI para el resultado sobre la ETH destaca por su transparencia. Un grupo encabezado por Russell Impagliazzo y Ramamohan Paturi, de la Universidad de California en San Diego —dos de los tres investigadores que propusieron la ETH hace un cuarto de siglo— y por Ryan Williams, del Instituto Tecnológico de Massachusetts (MIT), comprobará y explicará el resultado de forma independiente.

Williams anunció su participación en X, antes Twitter. Los tres publicaron además una carta abierta a la comunidad de ciencias de la computación teórica en la que explicaron con claridad qué significa su participación y qué no significa.

"Nuestra participación no debe interpretarse como una certificación de la afirmación. Un resultado de esta importancia requiere un escrutinio cuidadoso e independiente", escribieron Impagliazzo, Paturi y Williams.

Williams confirmó que el grupo no firmó acuerdos de confidencialidad y que no recibirá pagos. Los investigadores hicieron dos solicitudes a OpenAI: publicar todos los datos sin procesar relacionados con el resultado sobre la ETH y financiar una conferencia para que la comunidad tenga acceso directo al trabajo. OpenAI aceptó ambas. La compañía también entregó 5 millones de dólares a la Fundación Simons para talleres y conferencias sobre matemáticas producidas con IA.

Paturi dijo que su primera reacción al conocer el resultado fue de sorpresa. Participar en la revisión, añadió, no era opcional: sería impensable no examinar una afirmación de semejante importancia.

Para los resultados de física, el premio nobel David Gross encabeza un grupo de revisión separado junto con Michael Douglas, Arthur Jaffe, Igor Klebanov y Nikita Nekrasov. Ese grupo adoptó un enfoque más cauteloso que el panel de teoría de la complejidad: decidió no publicar los materiales producidos por IA y redactará por su cuenta el trabajo sobre física.

Claude también llegó al resultado, el mismo día

Horas después de que se hiciera público el anuncio de OpenAI, Anthropic publicó su propio artículo, titulado "Un algoritmo de tiempo 2^o(n) para 3-SAT", atribuido simplemente a "Claude (Anthropic)". El texto presenta un algoritmo determinista para 3-SAT y para el problema más difícil de conteo #3-SAT, en tiempo subexponencial, lo que contradice directamente la ETH por la misma lógica empleada en el resultado de OpenAI.

Según Levent Alpoge, investigador de Anthropic, Claude encontró el descubrimiento central el 16 de octubre mediante 14 millones de tokens de salida, sin intervención humana en el descubrimiento. Después, investigadores de Anthropic trabajaron con Claude para mejorar la presentación del resultado.

Al parecer, ninguno de los dos laboratorios sabía en qué estaba trabajando el otro. El artículo de Anthropic reconoce en una nota al pie el resultado simultáneo de OpenAI y señala que un modelo interno de esa empresa afirma haber demostrado un resultado similar. Según los relatos de ambas compañías, los dos sistemas llegaron a la misma conclusión algorítmica en una ventana de días aparentemente coincidente. En la historia de las matemáticas, coincidencias de este tipo suelen indicar que las herramientas necesarias para resolver un problema se han vuelto accesibles para cualquiera que trabaje lo suficiente en él.

El matemático Jelani Nelson, quien revisó de manera independiente la prueba de Claude, dijo que ambas pruebas parecen alcanzar aproximadamente el mismo límite asintótico de tiempo: exp(O(n / sqrt(log n))). Esto sugiere que los dos algoritmos están estrechamente relacionados en su técnica, aunque hayan abordado el problema de forma independiente.

La refutación de Claude tiene una diferencia técnica frente a la de OpenAI: también refuta la hipótesis del tiempo fuertemente exponencial (SETH), una versión más estricta de la ETH, porque la SETH implica lógicamente la ETH. El artículo de Claude también muestra que el resultado implica algoritmos teóricos más rápidos para una familia de problemas relacionados, entre ellos Independent Set, Clique, Vertex Cover y Dominating Set.

Qué garantiza —y qué no— la verificación en Lean

Las dos pruebas están formalizadas en Lean 4. Esto significa que una máquina verificó que cada paso lógico se desprende de las premisas establecidas dentro del sistema formal. Lo que Lean no puede garantizar —una distinción cada vez más importante a medida que se multiplican las matemáticas producidas por IA— es que la formalización sea una traducción semánticamente fiel de la demostración en lenguaje natural escrita por la IA.

El artículo de Anthropic añade una comprobación independiente: nanoda, un segundo núcleo de demostración escrito en Rust por desarrolladores distintos, confirmó todas las declaraciones de la prueba de Claude en Lean. El uso de un segundo núcleo, desarrollado en otro lenguaje de programación por otro equipo, permite detectar clases de errores que el propio verificador de Lean podría pasar por alto. Anthropic utilizó el mismo enfoque de dos núcleos para su formalización anterior del último teorema de Fermat.

El artículo de Anthropic también reconoce expresamente una limitación en una nota al pie: el desarrollo en Lean fue escrito por una IA y revisado únicamente por otras instancias de los mismos modelos. Hasta la fecha de publicación, no se conocía que ninguna persona lo hubiera comprobado manualmente. La maquinaria formal confirmó que la lógica es internamente consistente, pero no se ha confirmado que un matemático haya revisado línea por línea el argumento de Claude.

Investigadores han documentado desajustes en formalizaciones de IA en Lean: casos en los que una prueba traducida por una IA compila correctamente en Lean, pero no corresponde al argumento original en lenguaje natural. Por ello, una compilación exitosa puede coexistir con una prueba escrita defectuosa. La revisión de Impagliazzo, Paturi y Williams busca aportar la capa de comprensión que Lean no puede ofrecer: determinar si la estrategia de la prueba realmente hace lo que afirma y si la formalización representa correctamente esa estrategia.

Qué significa un algoritmo subexponencial para SAT —y qué no significa

Ambas pruebas son resultados asintóticos, y los dos artículos explican claramente lo que esto implica en la práctica.

La refutación de la ETH establece que existe un algoritmo que resuelve 3-SAT en tiempo subexponencial, es decir, que crece más lentamente que cualquier función exponencial del número de variables. Esto contradice directamente lo que la ETH consideraba imposible. Sin embargo, el algoritmo no ofrece una mejora significativa para ningún problema que un computador pueda resolver de manera realista. Según el artículo de Anthropic, el punto de equilibrio —el tamaño mínimo a partir del cual el algoritmo supera realmente una búsqueda exhaustiva sencilla— requiere aproximadamente 10^10.000 variables. La búsqueda por fuerza bruta ya se vuelve impracticable alrededor de las 100 variables. Como señala Anthropic, el resultado no dice nada sobre la resolución práctica de fórmulas.

La refutación tampoco acerca al campo a la solución de P vs. NP, la pregunta abierta más conocida de la informática. P vs. NP pregunta si existen algoritmos de tiempo polinómico para todos los problemas de la clase NP, una exigencia mucho más fuerte que la mera subexponencialidad. La ETH siempre fue un fortalecimiento de P ≠ NP, no una afirmación equivalente. El propio presidente de OpenAI dijo que probablemente P sigue siendo distinta de NP.

Lo que sí hace la refutación, si supera la revisión, es obligar a examinar una enorme cantidad de trabajos existentes. El artículo de Anthropic encontró que los límites inferiores basados en la ETH sustentan 800 artículos sobre teoría de grafos, optimización de consultas en bases de datos, complejidad parametrizada y complejidad de la comunicación. Las conclusiones prácticas de esos trabajos no necesariamente serían erróneas, pero la justificación formal en la que muchos se apoyaron dejaría de sostenerse. Los investigadores de cada subcampo tendrían que establecer si sus resultados específicos pueden reconstruirse sobre fundamentos diferentes.

Quién recibe el crédito y por qué no hay una respuesta sencilla

El descubrimiento independiente y simultáneo plantea una cuestión de reconocimiento que ninguna de las dos compañías puede resolver por sí sola.

En su carta abierta a los teóricos de la complejidad, Impagliazzo, Paturi y Williams señalaron el problema estructural: el reconocimiento en las matemáticas de la era de la IA podría inclinarse hacia quien publique primero o tenga acceso a las herramientas computacionales más potentes, mientras recibe menos atención el trabajo minucioso de comprobar una prueba, explicarla a la comunidad y construir nuevos resultados sobre ella. La preocupación hace eco de otra planteada en la Declaración de Leiden, en junio de 2026, cuando un grupo de matemáticos respaldado por la Unión Matemática Internacional pidió nuevas normas sobre la atribución en trabajos realizados con IA.

La respuesta de OpenAI es renunciar al reconocimiento: la empresa ha dicho que no buscará crédito académico por los descubrimientos y que este debe corresponder a los investigadores que expliquen y verifiquen el trabajo. También aportó 5 millones de dólares a la Fundación Simons para financiar talleres y conferencias en los que la comunidad pueda analizar directamente los resultados producidos por IA.

La Asociación de Matemáticas Humanas, creada después de la publicación matemática de OpenAI del 6 de octubre y que pidió a los matemáticos dejar de trabajar con la compañía por preocupaciones sobre la atribución de resultados generados por IA, aún no se ha pronunciado públicamente sobre si el proceso estructurado de revisión de la ETH —con revisores independientes, identificados y no remunerados, y sin acuerdos de confidencialidad— responde a esas inquietudes.

Qué sigue

La infraestructura matemática para verificar resultados de este tipo se está construyendo en tiempo real. En colaboración con el investigador de Anthropic Levent Alpoge, el matemático Ethan Sussman, de la Universidad Northwestern, creó un repositorio público en GitHub dedicado a la comprobación independiente del resultado sobre la ETH.

El panel de Impagliazzo, Paturi y Williams será la primera señal de autoridad para el campo. Un dictamen positivo de los científicos que propusieron la ETH confirmaría que el 16 de octubre de 2026 fue un punto de inflexión genuino para la teoría de la complejidad computacional. Un error en la prueba en lenguaje natural, en la formalización en Lean o en la correspondencia entre ambas indicaría a la comunidad dónde se produjo el fallo y dejaría abierta la cuestión.

Hasta que llegue ese dictamen, la refutación de la ETH y su gemela simultánea ocupan una posición epistemológica inusual: están verificadas por una máquina dentro de un sistema formal, disponibles públicamente para su inspección, reconocidas por los principales expertos del campo como afirmaciones que requieren un escrutinio cuidadoso e independiente y, potencialmente, tienen consecuencias suficientes para cambiar una parte importante de la informática teórica si la prueba resulta correcta. Impagliazzo, Paturi y Williams lo expresaron así en su carta abierta a los investigadores.

Preguntas frecuentes

¿Qué es la Hipótesis del Tiempo Exponencial y por qué importa saber si es cierta?

La Hipótesis del Tiempo Exponencial (ETH) es una conjetura matemática de 1999 según la cual 3-SAT —el problema lógico canónico en el centro de la NP-completitud— no puede resolverse de manera significativa más rápido que en tiempo exponencial. Más de 800 artículos de investigación utilizaron la ETH como fundamento para demostrar que problemas específicos de teoría de grafos, biología computacional, bases de datos y otros campos son computacionalmente difíciles y que los algoritmos conocidos para resolverlos son esencialmente óptimos. Si la ETH es falsa, esas justificaciones formales deben reconsiderarse, aunque eso no significa automáticamente que los problemas pasen a ser fáciles de resolver.

¿Refutar la ETH significa que la IA resolvió P vs. NP?

No. P vs. NP pregunta si existen algoritmos de tiempo polinómico para todo problema que pueda verificarse en tiempo polinómico. La refutación de la ETH establece únicamente que existe un algoritmo subexponencial para 3-SAT, una afirmación más débil. La ETH siempre fue una afirmación más fuerte que P ≠ NP, y refutarla no dice nada sobre si P es igual a NP. El propio presidente de OpenAI afirmó que probablemente P sigue siendo distinta de NP. La refutación tampoco produce un algoritmo prácticamente más rápido para tamaños de problema realistas.

Si Lean ya verificó las dos pruebas, ¿por qué hace falta una revisión humana independiente?

Lean comprueba que el término de la prueba formal es lógicamente consistente dentro de su sistema de axiomas. No verifica que la formalización en Lean capture correctamente el argumento en lenguaje natural producido por la IA. Investigadores han documentado casos en los que sistemas de IA generaron formalizaciones desajustadas en Lean: una compilación aprobada puede coexistir con un argumento escrito defectuoso. La revisión de Impagliazzo, Paturi y Williams busca aportar la comprensión que Lean no puede ofrecer: establecer si la estrategia de la prueba hace realmente lo que afirma y si la formalización representa adecuadamente esa estrategia.

Cuando dos sistemas de IA producen el mismo descubrimiento el mismo día, ¿quién recibe el crédito?

Aún no existe consenso, y ese es precisamente el problema estructural planteado por la carta abierta de Impagliazzo, Paturi y Williams. OpenAI y Anthropic han renunciado al reconocimiento académico y han dirigido el crédito hacia los investigadores que verifiquen y expliquen el trabajo. Pero la cuestión va más allá: la comunidad todavía está desarrollando normas sobre cómo citar resultados producidos por IA, si los investigadores que los verifican deben convertirse en autores de los artículos y cómo deben tratar las revistas las pruebas generadas por máquinas. Tanto la Declaración de Leiden como la Asociación de Matemáticas Humanas han promovido estándares explícitos de atribución. Es probable que el descubrimiento doble de la ETH acelere esa conversación.