✨︎ Resumen (TL;DR):
- Fabio Dias y Yvens Lima calcularon los límites del algoritmo con el que OpenAI busca refutar la hipótesis del tiempo exponencial.
- Con una constante supuesta de 2, la mejora frente a la búsqueda exhaustiva aparecería cerca de 10^32 variables.
- El análisis no demuestra que la propuesta acelere problemas SAT reales, el diseño de chips o permita romper RSA en condiciones prácticas.
Un preprint de Fabio Dias y Yvens Lima concluye que, en las condiciones estudiadas, las cotas de tiempo del algoritmo presentado por OpenAI para refutar la hipótesis del tiempo exponencial (ETH) no garantizan una mejora frente a la búsqueda exhaustiva. Publicado el 31 de octubre de 2026, el trabajo analiza la utilidad teórica de la propuesta, no la velocidad de un producto comercial ni la validez definitiva de la supuesta refutación.
OpenAI anunció el 26 de octubre de 2026 que un modelo interno había producido el resultado. La compañía informó que el trabajo se formalizó con Lean, una herramienta para comprobar demostraciones matemáticas, y puso el material a disposición de investigadores.
El preprint de Dias y Lima examina qué puede deducirse de las cotas presentadas por OpenAI. No es una medición directa de la velocidad de un producto comercial ni una certificación de que la supuesta refutación sea correcta.
ETH mide el crecimiento, no la velocidad inmediata
La hipótesis del tiempo exponencial (ETH) es una hipótesis de complejidad computacional que sostiene que, en el peor caso, el tiempo necesario para resolver 3-SAT crece exponencialmente con el número de variables.
3-SAT es un problema lógico que pregunta si se pueden asignar valores de verdadero o falso a una serie de variables para que se cumplan todas las condiciones de una fórmula.
El manuscrito de OpenAI propone un algoritmo que cuenta las asignaciones que satisfacen la fórmula. Si el argumento se confirma, ese conteo también permitiría responder si existe al menos una solución y, con ello, refutar ETH.
Subexponencial es un término de complejidad que describe cómo crece el costo cuando aumenta el tamaño del problema. No significa que el algoritmo sea rápido para los tamaños usados en la práctica. Las constantes que acompañan una cota también influyen en el punto en que esa garantía puede superar otra forma de cálculo.
El umbral de 10^32 depende de una suposición
Como OpenAI no especificó una de esas constantes, Dias y Lima asumieron que valía 2. Bajo esa premisa, calcularon que una cota general solo mejoraría la búsqueda exhaustiva a partir de aproximadamente 10^32 variables, es decir, un 1 seguido de 32 ceros.
La cifra depende de la suposición y describe lo que garantiza la cota. No fija una frontera absoluta a partir de la cual el algoritmo empiece a funcionar. Además, la comparación usa la búsqueda exhaustiva como referencia, aunque ya existen métodos más eficientes para resolver casos de SAT.
En una demostración para fórmulas con una proporción acotada de cláusulas por variable, los autores calcularon que la garantía de tiempo tampoco supera la búsqueda exhaustiva para entradas de tamaño que pueda escribirse de manera explícita. Esto no descarta por sí solo que otra implementación o un avance posterior consiga mejores resultados.
Chips y RSA están en otra capa
Los problemas de satisfacibilidad también aparecen en tareas de diseño. Una investigación recopilada por IBM Research describe el uso de un algoritmo SAT en el diseño de circuitos asíncronos. Encontrar métodos más útiles para ciertas fórmulas podría abrir oportunidades en ese trabajo, pero el análisis de Dias y Lima no demuestra que la propuesta de OpenAI acelere esas herramientas.
El cifrado exige separar los problemas. RSA es un ejemplo de criptografía asociada con la factorización de números enteros, según el Instituto Nacional de Estándares y Tecnología de Estados Unidos, NIST. Una cota nueva para 3-SAT no demuestra por sí sola que sea posible romper RSA en condiciones prácticas.
El manuscrito de OpenAI advierte que trasladar el resultado a otro problema requiere una reducción adecuada que controle el tamaño de la fórmula resultante. Confirmar la refutación de ETH y encontrar una aplicación capaz de comprometer un cifrado concreto serían, por tanto, pasos distintos.
Lean facilita la revisión, no la cierra
Russell Impagliazzo y Ramamohan Paturi, quienes participaron en la formulación de ETH, se sumaron a Ryan Williams para organizar el examen del resultado. En una carta a la comunidad, los tres investigadores precisaron que su participación no debe interpretarse como una certificación y pidieron una revisión independiente.
La comprobación formal en Lean ayuda a revisar los pasos expresados en ese lenguaje. La comunidad también debe examinar cómo se relacionan las definiciones formalizadas con la afirmación matemática y qué consecuencias se desprenden de ella.
Si la refutación se confirma, los resultados que dependen de ETH tendrán que reconsiderar ese supuesto. La propuesta tampoco resuelve el problema P frente a NP: una cota subexponencial no equivale a demostrar que el problema pueda resolverse en tiempo polinómico.
El análisis de Dias y Lima separa dos preguntas: si el resultado teórico resiste la revisión y si sus cotas pueden convertirse en una herramienta que mejore cálculos reales. Por ahora, la propuesta de OpenAI no ofrece una garantía práctica frente a la búsqueda exhaustiva para problemas de tamaño manejable.
