OpenAI ha publicado un artículo de matemáticas cuyo título afirma que la Exponential Time Hypothesis es falsa. Si la demostración se sostiene, elimina uno de los supuestos de trabajo de la informática teórica moderna: que los problemas lógicos más difíciles de un tipo estándar no se pueden resolver mucho más rápido que probando todas las posibilidades. Muchísimos resultados de dificultad publicados se apoyan en esta hipótesis, así que una refutación confirmada obligaría a replantear todo el campo.
El artículo, fechado el 17 de octubre y revisado el 25 de octubre de 2026, está publicado en el repositorio público de matemáticas de OpenAI en GitHub y se atribuye solo a OpenAI, sin autores individuales. El repositorio indica que sus manuscritos los produjo un modelo interno de OpenAI sin nombre y que deben tratarse como datos de investigación en bruto, no como artículos terminados. A lo largo de más de 60 páginas, su teorema principal da un algoritmo determinista que cuenta todas las asignaciones que satisfacen una fórmula k-CNF, una fórmula lógica formada por cláusulas de como mucho k términos, para cualquier k fijo igual o mayor que 2. El tiempo de ejecución crece aproximadamente como 2 elevado a n dividido por la raíz cuadrada de log n, donde n es el número de variables, y el uso de memoria sigue siendo polinómico. Eso es más lento que el tiempo polinómico pero más rápido que cualquier 2 elevado a una constante por n, que es justo lo que la hipótesis descarta. Contar soluciones es más difícil que decidir si existe alguna, de modo que el resultado refuta también la versión de conteo de la hipótesis y, según sostiene el artículo, sus variantes más fuertes.
El método es algebraico. Según nuestra lectura de la introducción, divide las variables en grupos, convierte la fórmula en ecuaciones polinómicas de grado bajo y cuenta sus ceros comunes mediante interpolación y sumas rápidas, a partir de técnicas anteriores de dividir y listar y de inclusión-exclusión. El artículo enumera consecuencias: conteo exacto subexponencial de coloraciones de grafos, conjuntos independientes y emparejamientos perfectos, y esquemas de aproximación para Max-k-SAT. Tiene cuidado en aclarar que esto no da algoritmos rápidos para todos los problemas NP, porque las cotas de tiempo de esta forma no se trasladan a través de las reducciones habituales.
El contexto obliga a la cautela. Los mejores contadores exactos anteriores para 3-SAT seguían funcionando en un tiempo claramente exponencial, y décadas de trabajo, incluidos el algoritmo PPSZ y sus refinamientos, solo lograron rebajar la base del exponente poco a poco. Uno de los corolarios del artículo depende además de otro preprint de OpenAI, The Unique Games Theorem, de septiembre, que tampoco ha sido revisado.
Nada de esto ha pasado una revisión por pares, el propio repositorio de OpenAI advierte de que los resultados sin una demostración formal en Lean podrían contener errores, y no hemos visto respuestas publicadas de especialistas en complejidad. Resultados de este tamaño se han anunciado y retirado antes, a menudo por un hueco que solo apareció cuando los especialistas repasaron cada lema. La postura adecuada por ahora es interés sin fe: el artículo es lo bastante detallado para que los especialistas lo comprueben paso a paso, y su veredicto zanjará la cuestión antes que cualquier comentario.