Durante casi tres décadas, una de las ideas fundamentales de la informática teórica parecía mantenerse fuera de discusión: determinados problemas matemáticos necesitan un tiempo de cálculo que crece de forma exponencial a medida que aumenta su complejidad. Sobre esa premisa se construyeron cientos de investigaciones y métodos para determinar qué problemas pueden resolver las computadoras. Ahora, OpenAI y Anthropic aseguran haber encontrado, mediante inteligencia artificial, demostraciones matemáticas que contradicen aquella hipótesis. Y la reacción de los científicos combina entusiasmo, desconcierto y una preocupación bastante comprensible: una parte de su trabajo podría necesitar una revisión profunda.
La controversia comenzó el 26 de octubre, cuando OpenAI anunció que sus modelos habían refutado la denominada Hipótesis del Tiempo Exponencial (ETH). Poco después, Anthropic presentó una demostración independiente. Según explicó WIRED , algunos investigadores consideran que, si las pruebas resisten el análisis científico, estaríamos ante uno de los resultados más importantes de una generación en su especialidad. Una hipótesis de 27 años que parecía marcar los límites de lo que pueden calcular las computadoras Una composición conceptual sobre el azar, la probabilidad y las matemáticas.
La posible refutación de la Hipótesis del Tiempo Exponencial podría obligar a revisar numerosas investigaciones sobre la complejidad de los problemas computacionales. © Artemio López. La Hipótesis del Tiempo Exponencial fue formulada en 1999 por Russell Impagliazzo y Ramamohan Paturi . En términos sencillos, sostiene que ciertos problemas de satisfacibilidad lógica, conocidos como 3-SAT, no pueden resolverse mediante algoritmos cuyo tiempo de ejecución crezca de manera subexponencial respecto al número de variables. Durante años, esta suposición permitió establecer límites teóricos sobre la dificultad de numerosos problemas informáticos.
La demostración publicada por OpenAI en GitHub propone un algoritmo determinista que puede contar las soluciones de determinadas fórmulas booleanas en tiempo subexponencial. Eso contradice directamente la hipótesis original, siempre que la prueba sea correcta. La diferencia es importante: el algoritmo no convierte automáticamente esos problemas en tareas fáciles de resolver. Tampoco demuestra que P sea igual a NP, uno de los mayores interrogantes de la informática.
Lo que cuestiona es una barrera teórica que durante décadas se consideró fundamental. Según TechCrunch , ambas compañías publicaron sus resultados junto con formalizaciones en Lean, un lenguaje que permite comprobar matemáticamente la coherencia de las demostraciones. Sin embargo, que una prueba supere esa verificación no garantiza por sí solo que la formulación corresponda exactamente al problema original ni que los especialistas hayan validado todas sus implicaciones. Algunos investigadores podrían tener que revisar décadas de trabajo, pero otros celebran el resultado Ejemplo de una demostración matemática formalizada en Lean, un sistema que permite comprobar pruebas mediante software.
OpenAI y Anthropic utilizaron esta tecnología para formalizar sus resultados sobre la Hipótesis del Tiempo Exponencial. © Leonardo de Moura. Uno de los casos más llamativos es el de Peter Jonsson, profesor de la Universidad de Linköping , en Suecia. Su equipo tenía previsto presentar una investigación en el prestigioso Simposio IEEE sobre Fundamentos de la Informática . Sin embargo, el nuevo resultado podría invalidar parte de las premisas utilizadas en aquel trabajo.
En declaraciones a WIRED , Jonsson reconoció que la situación resulta frustrante, pero también representa una oportunidad científica extraordinaria. Otros investigadores comparten esa sensación. Daniel Lokshtanov, de la Universidad de California en Santa Bárbara , calcula que alrededor de 50 artículos propios podrían necesitar revisión si la refutación se confirma. Thore Husfeldt, especialista en algoritmos de la Universidad de Tecnologías de la Información de Copenhague , describió el acontecimiento como una oportunidad excepcional para explorar cuestiones que antes parecían cerradas.
Al mismo tiempo, advirtió sobre el impacto psicológico que está teniendo la creciente cantidad de descubrimientos anunciados mediante inteligencia artificial. La preocupación no se limita a que las máquinas encuentren respuestas antes que los humanos. También existe un problema de escala: los investigadores reciben enormes cantidades de demostraciones y manuscritos que necesitan tiempo para comprobar, interpretar y contextualizar. La cobertura de The Verge recoge precisamente cómo OpenAI está intentando organizar grupos académicos para examinar algunos de sus resultados más ambiciosos.
Por ahora, Russell Impagliazzo, Ramamohan Paturi y Ryan Williams, del MIT , están impulsando una revisión independiente. Su participación no implica que hayan certificado la refutación. También deben evaluarse las posibles consecuencias para la criptografía y el desarrollo de algoritmos, aunque no existe evidencia de que los sistemas actuales de seguridad digital hayan quedado comprometidos. El episodio deja una paradoja difícil de ignorar: herramientas informáticas desarrolladas utilizando décadas de conocimiento teórico podrían haber contribuido a cuestionar una de las ideas sobre las que se apoyó ese mismo conocimiento .
Si las demostraciones resultan correctas, el acontecimiento no significará el final de la informática teórica, sino el comienzo de una etapa en la que muchas preguntas que parecían respondidas volverán a estar abiertas.
