Un algoritmo que cuenta las soluciones de cualquier fórmula 3-SAT en tiempo subexponencial: eso es lo que afirma el preprint "The Exponential Time Hypothesis is False", firmado solo por OpenAI y publicado el 26 de octubre de 2026. Si aguanta la revisión, cae una de las hipótesis sobre las que se ha construido buena parte de la complejidad computacional de los últimos 25 años. Lo ha producido un modelo interno que OpenAI no ha lanzado, y un grupo de investigadores independientes ya lo está examinando.
Qué dice el resultado
La Hipótesis del Tiempo Exponencial (ETH) sostenía que decidir 3-SAT con n variables exige, en el peor caso, tiempo 2^Ω(n): ningún truco puede quitarle al exponente su crecimiento lineal. El artículo presenta un algoritmo determinista que cuenta exactamente las asignaciones que satisfacen una fórmula k-CNF, para cualquier k fijo, con espacio polinómico y un exponente del orden de n / (log n)^(1/2+o(1)). Saber si el recuento es mayor que cero ya resuelve la satisfacibilidad, así que el exponente deja de ser lineal en n.
El propio artículo enumera lo que cae con él: ETH, la versión fuerte (SETH), Gap-ETH, NSETH y la variante de conteo (#ETH). También deriva algoritmos subexponenciales para contar coloraciones de grafos, conjuntos independientes y emparejamientos perfectos.
Cómo queda frente a lo mejor conocido
| Problema | Mejor resultado previo que cita el artículo | Lo que afirma OpenAI |
|---|---|---|
| 3-SAT, determinista | O(1,32793^n), Liu (2018) | 2^o(n) |
| 3-SAT, aleatorizado | O*(1,307^n), preprint de Jiang y Cai (2026) | 2^o(n), y determinista |
| Contar soluciones de 3-SAT | O*(1,637^n), Kutzkov (2026) | 2^o(n) |
Todos los algoritmos anteriores eran exponenciales con una base algo menor que 2. El nuevo cambia la forma del exponente. La técnica es algebraica: reparte las variables en grupos y sustituye las cláusulas por polinomios de grado bajo que comparten unas pocas "medidas", de modo que las contribuciones de cada grupo se multiplican de forma independiente.
Por qué le importa a un ingeniero
No va a acelerar tu solver SAT ni tu planificador de recursos a corto plazo. Es un resultado asintótico, con constantes ocultas en la notación O que dependen de k, y la ganancia en el exponente es un factor del orden de la raíz de log n.
Lo que sí cambia es el mapa de lo que creemos imposible. Durante años, SETH ha sido el argumento para decir que la distancia de edición, la subsecuencia común más larga, la distancia de Fréchet o el matching de expresiones regulares no admiten algoritmos sustancialmente más rápidos que los cuadráticos de siempre. El artículo reconoce que algunas de esas cotas siguen en pie porque se apoyan en hipótesis más débiles, como la de vectores ortogonales (OVC), pero otras pierden su base. En criptografía, el apéndice C muestra que las versiones de localidad constante de las funciones unidireccionales candidatas de Goldreich se pueden invertir en tiempo 2^o(n), aunque deja claro que eso no rompe su seguridad frente a algoritmos polinómicos.
Para quien construye con IA, el titular es otro: un modelo ha producido una demostración que, de confirmarse, resuelve una conjetura central de la informática teórica. Forma parte del repositorio openai/math, que ya reúne 721 manuscritos en 373 familias, generados tras plantear al modelo unos 4.000 problemas con una media de tres horas de cómputo por resultado.
La cautela que importa
Es un preprint sin revisión por pares. OpenAI ha pedido a un grupo encabezado por Russell Impagliazzo, Ramamohan Paturi y Ryan Williams, tres nombres clave en el estudio de ETH, que examine y explique la prueba, y ha publicado los materiales de inmediato a petición del propio grupo. El historial del repositorio invita a esperar: el 7 de octubre de 2026 retiró tres manuscritos por un error de signo y corrigió otros 14. La misma entrega del 26 de octubre incluye además un resultado de análisis armónico sobre las conjeturas de Kakeya.