OpenAI y Anthropic afirman que sus modelos refutaron una hipótesis clave de la informática

OpenAI publicó soluciones a tres problemas matemáticos de larga data, entre ellos una refutación sorpresiva de la Hipótesis del Tiempo Exponencial (ETH, por sus siglas en inglés), un supuesto fundamental de la informática sobre cuán difícil es resolver ciertos problemas. Como ocurrió con publicaciones anteriores del laboratorio, la reacción combinó entusiasmo e inquietud: el matemático de Anthropic Levent Alpöge argumentó que las soluciones de OpenAI se apoyaban en trabajo ya existente, y horas después Anthropic publicó su propia refutación de la ETH.

Esta vez, OpenAI varió su despliegue según la disciplina: publicó los resultados matemáticos en GitHub, ofreció a los informáticos un grupo de trabajo y financiamiento para una conferencia sobre las pruebas, y dejó que los físicos formaran su propio grupo de trabajo para decidir cómo divulgar su resultado. El cambio se produjo tras las críticas del profesor del MIT Ryan Williams, quien encabeza la respuesta del campo de la informática y había comparado antes un volcado de pruebas de OpenAI a principios de octubre con un ataque de denegación de servicio contra los matemáticos. Aun así, Williams aceptó ayudar a interpretar el nuevo resultado, junto con Russell Impagliazzo y Ramamohan Paturi, de UC San Diego, quienes publicaron el artículo original de la ETH en 1999; el primer paso del grupo fue una carta abierta en la que pidieron a la comunidad opiniones sobre las matemáticas y sobre las normas para las contribuciones de la IA a ese trabajo.

La ETH forma parte de la pregunta más amplia de P contra NP: si todo problema cuya solución es fácil de verificar (NP) también es fácil de encontrar (P), la lógica detrás de la criptografía, donde leer un mensaje ya descifrado es trivial, pero descifrar el código no lo es. La mayoría de los científicos asume que P no es igual a NP, y la ETH respaldaba ese supuesto al sostener que ningún algoritmo puede resolver una clase específica de rompecabezas lógicos difíciles sin que el tiempo necesario crezca de forma exponencial a medida que crece el rompecabezas. OpenAI y Anthropic afirman que sus modelos produjeron algoritmos capaces de resolver esos rompecabezas en tiempo “subexponencial”, más rápido de lo que se creía posible, y que, si el resultado se confirma, refutaría la ETH y podría abrir un camino hacia demostrar que P es igual a NP.

“Es probable que todo informático deba darle algo más de peso a la plausibilidad de que P = NP, aunque ese peso puede variar para cada uno”, dijo Williams, quien además duda que el algoritmo de OpenAI sea el mejor que existe. El resultado amenaza con poner en duda una década de artículos construidos sobre la durabilidad de la ETH, razón por la cual Williams presionó a OpenAI para que financiara una conferencia sobre las consecuencias. También planteó una preocupación más inmediata: si un algoritmo más rápido rompe sistemas criptográficos que dependen de ciertos tamaños de clave. Dijo que le planteó esa pregunta directamente a Dan Roberts, responsable científico de OpenAI, y que el laboratorio lo verificó y respondió con una confianza razonable de que nada se había roto. Williams dice que sigue siendo optimista sobre el papel cada vez mayor de la IA en la investigación, aunque esto obligue a los científicos a elevar el nivel de las preguntas que se plantean.

Por qué importa

Si los algoritmos subexponenciales resisten el escrutinio, una década de artículos construidos sobre la durabilidad de la ETH, y posiblemente algunos sistemas criptográficos que dependen de ella, tendrían que revisarse, lo que subraya la velocidad con la que los laboratorios de IA pueden hoy desestabilizar campos considerados fundamentales.