OpenAI y Anthropic han publicado resultados generados por IA que afirman refutar la hipótesis del tiempo exponencial, una conjetura de larga data en la teoría de la complejidad computacional.
El 26 de octubre, OpenAI anunció que sus modelos habían producido una demostración de que la hipótesis del tiempo exponencial es falsa. La hipótesis, propuesta a principios de la década de 2000, sostiene que 3-SAT no puede resolverse en tiempo subexponencial; es decir, que algunos rompecabezas lógicos comunes no pueden resolverse mucho más rápido que probando por fuerza bruta todas las respuestas posibles.
Dado que la hipótesis ha sido ampliamente aceptada y utilizada en cientos de artículos para obtener resultados condicionales de dificultad computacional en una gran variedad de campos, refutarla invalidaría una parte importante de esos resultados y obligaría a los investigadores a reevaluar la dificultad computacional de problemas en áreas como los algoritmos, la teoría de grafos y la biología computacional.
La empresa de IA afirmó que sus modelos generaron la refutación en lenguaje natural el 16 de octubre y la formalizaron en el asistente de demostración matemática Lean al día siguiente; ambos resultados están disponibles en un repositorio público de GitHub.
OpenAI señaló que el trabajo está siendo examinado por un grupo externo dirigido por Russell Impagliazzo y Ramamohan Paturi, de UC San Diego —dos de los autores originales de la hipótesis—, y Ryan Williams, del MIT.
En X, Williams declaró que los investigadores aún están tratando de determinar las implicaciones prácticas del descubrimiento.
«Al ritmo actual de progreso, es posible que veamos una actualización importante sobre la resolución práctica de SAT en los próximos 12 meses. O quizá no veamos nada parecido. La verdad es que no lo sé», afirmó Williams.
Por separado, Anthropic publicó un artículo y una formalización en Lean 4 en los que se afirma que un algoritmo determinista resuelve 3-SAT de una manera que refutaría la hipótesis del tiempo exponencial. La empresa afirmó que un modelo interno de investigación de Claude descubrió el algoritmo central el 16 de octubre —el mismo día en que los modelos de OpenAI hicieron el descubrimiento— utilizando 14 millones de tokens de salida sin intervención humana.
«El resultado es puramente asintótico y no dice nada sobre la resolución de fórmulas en la práctica», señaló Anthropic.
Mientras tanto, OpenAI también presentó otros dos resultados generados por IA: una demostración de la conjetura del suavizado local en todas las dimensiones en el análisis armónico y una demostración matemáticamente rigurosa de la existencia de ciertas teorías cuánticas de campos, incluidas la cromodinámica cuántica y la teoría pura de Yang-Mills.