OpenAI ha publicado un artículo de 67 páginas afirmando que la IA de la empresa refutó la Hipótesis del Tiempo Exponencial (ETH). La conjetura data de 1999 y no tiene ninguna conexión con ethereum, el precio de ethereum ni su cofundador Vitalik Buterin. El reclamo generó discusiones entre matemáticos y usuarios de criptomonedas en X. Un usuario de X, Takumi, bromeó: "Malditos traders algorítmicos acaban de masacrar $ETH". Andrew Jiang escribió: "Vitalik ha estado muy callado desde que salió esto".
Los científicos de la computación Russell Impagliazzo, Ramamohan Paturi y Francis Zane propusieron ETH. La conjetura sostiene que resolver el problema lógico 3-SAT no puede ser mucho más rápido que probar cada combinación. El problema 3-SAT requiere encontrar asignaciones de verdadero-o-falso que satisfagan reglas que involucran tres opciones a la vez. OpenAI afirma que cientos de artículos dependen de ETH para establecer límites computacionales en teoría de grafos, biología computacional, bases de datos y geometría. OpenAI argumenta que refutar ETH reabre preguntas sobre posibles mejoras de velocidad y podría dirigir la investigación hacia algoritmos más eficientes.
El documento lleva la fecha de 17 de octubre y una fecha de revisión del 25 de octubre. El documento presenta un algoritmo determinista, que no utiliza aleatoriedad, para contar todas las asignaciones satisfactorias en tiempo subexponencial. Tiempo subexponencial significa que el trabajo requerido aumenta más lentamente que cualquier función exponencial del número de variables. Contar asignaciones satisfactorias es más difícil que determinar si existe alguna asignación satisfactoria, por lo que el algoritmo de conteo también aborda el problema de decisión. OpenAI afirma que la IA descubrió la supuesta refutación el 16 de octubre. OpenAI dice que el resultado fue formalizado el 17 de octubre utilizando Lean, un software que verifica mecánicamente cada paso lógico. El documento y la formalización están disponibles en GitHub. OpenAI también publicó 722 manuscritos matemáticos a través de GitHub a principios de este mes, pero solo 162 incluían un resultado principal verificado por computadora.
Impagliazzo, Paturi y Ryan Williams del MIT lideran un examen independiente de la afirmación. Los tres investigadores advirtieron en una carta abierta que la participación no debe interpretarse como una certificación. Los investigadores señalaron que un hallazgo de tal importancia requiere una revisión independiente rigurosa y una explicación que otros investigadores puedan reproducir, cuestionar y desarrollar. OpenAI afirma que los participantes no reciben compensación y no firmaron acuerdos de confidencialidad. OpenAI ha aceptado liberar todos los datos crudos y financiar una conferencia sobre el resultado.
OpenAI advierte que identificar algoritmos útiles y traducir el progreso teórico en ganancias prácticas requerirá investigaciones adicionales sustanciales. El artículo no establece que todos los problemas NP admitan soluciones de tiempo subexponencial. P consiste en problemas que las computadoras pueden resolver eficientemente, mientras que NP consiste en problemas cuyas soluciones propuestas pueden verificarse eficientemente. El problema P versus NP, que pregunta si la verificación eficiente siempre implica una solución eficiente, sigue sin resolverse.
Anthropic publicó posteriormente un artículo atribuido a Claude, titulado "Un algoritmo de tiempo 2^o(n) para 3-SAT" y fechado el 26 de octubre. El repositorio acompañante indica que una versión interna de investigación de Claude descubrió el algoritmo, que también aborda ETH. El repositorio advierte que el resultado se refiere al comportamiento asintótico y no hace ninguna afirmación sobre la resolución práctica de fórmulas. Claude formalizó el Último Teorema de Fermat utilizando Lean en septiembre. El matemático Terence Tao advirtió en septiembre que incluso los rumores sobre investigación en un problema pueden provocar esfuerzos extensos asistidos por IA antes de que el proyecto original se desarrolle por completo.
OpenAI recientemente contribuyó $5 millones a la Fundación Simons. Esta contribución apoyará talleres, conferencias y programas especiales que ayudan a los investigadores a examinar y ampliar los resultados generados por la IA.