Los modelos de IA refutan la hipótesis del tiempo exponencial: ¿qué significa esto?

En pocos días, un viejo debate de las ciencias de la computación pasó de las salas de investigación al primer plano de la discusión tecnológica: ¿pueden los modelos de inteligencia artificial derribar una hipótesis que durante más de dos décadas fue piedra angular de nuestra comprensión de los límites de la computación? OpenAI anunció que había publicado soluciones a tres problemas matemáticos especialmente resistentes, el más destacado de los cuales era una refutación sorprendente de lo que se conoce como la «hipótesis del tiempo exponencial» (Exponential Time Hypothesis). Horas después de que varios investigadores objetaran la metodología del anuncio, Anthropic publicó su propia refutación de la misma hipótesis.

¿Qué es la hipótesis del tiempo exponencial?

Los investigadores Russell Impagliazzo y Ramamohan Paturi formularon esta hipótesis en 1999, y pertenece a una familia más amplia de preguntas conocida como el problema «P frente a NP». La esencia de la hipótesis es que cierta clase de acertijos lógicos difíciles solo puede resolverse mediante algoritmos cuyo tiempo se duplica de forma exponencial a medida que aumenta el número de variables; es decir, añadir unas pocas variables puede convertir un cálculo de minutos en uno de siglos.

Para aclarar el panorama general: el problema P frente a NP pregunta si todo problema cuya solución es fácil de verificar es también fácil de encontrar. El «sudoku» es un ejemplo sencillo: comprobar una cuadrícula completa es rápido, pero llegar a ella resulta costoso en tiempo. Esta disparidad no es un detalle académico, sino el fundamento sobre el que se sostienen los sistemas de cifrado modernos: quien posee la clave descifra el mensaje en un instante, y quien no la tiene necesita un tiempo inviable para romperlo.

Por eso la mayoría de los investigadores se inclina a creer que P ≠ NP, y la hipótesis del tiempo exponencial era uno de los indicios más sólidos en favor de esa creencia.

¿Qué dicen exactamente los dos laboratorios?

Ambas empresas afirman que sus modelos llegaron a algoritmos que resuelven esos acertijos en tiempo «subexponencial», es decir, más rápido que el límite que se creía imposible de superar. Si esto se confirma, la hipótesis quedaría refutada, lo que abre la puerta —teóricamente, no en la práctica hasta ahora— a reevaluar la posibilidad de que P = NP.

El profesor del MIT Ryan Williams, especialista en complejidad computacional, fue uno de los críticos más duros del método de OpenAI de publicar las demostraciones de golpe; de hecho, describió un anuncio anterior como algo parecido a un «ataque de denegación de servicio contra los matemáticos». Aun así, aceptó colaborar con los dos laboratorios para liderar la respuesta de la comunidad de ciencias de la computación, con la participación de Impagliazzo y Paturi. Williams señala que algunas partes de la demostración son «rutinarias», pero que hay dos o tres puntos que «parecen completamente extraños», y que son precisamente los que exigen un trabajo colectivo para comprenderlos.

Un cambio en la forma de publicar

Llama la atención que OpenAI haya tratado cada disciplina de manera distinta, lo que supone una evolución en su metodología:

• Matemáticas: publicación de los resultados directamente en GitHub.
• Ciencias de la computación: creación de un grupo de trabajo que exigió la publicación abierta de las demostraciones y la financiación de una conferencia especializada para debatirlas.
• Física: un grupo de trabajo determinará por sí mismo el mecanismo para anunciar el resultado.

También se publicó una carta abierta que invita a los investigadores a aportar sus observaciones y a debatir las normas profesionales que deben regular las contribuciones de la inteligencia artificial a la investigación científica, un punto no menos importante que el propio resultado matemático.

¿Está la criptografía en peligro?

La primera pregunta que planteó Williams no fue científica, sino de seguridad: ¿afecta el nuevo algoritmo a sistemas de cifrado existentes? Según lo que él mismo relató, OpenAI confirmó que había realizado la comprobación necesaria y que tiene una confianza razonable en que el resultado no permite romper ningún sistema de cifrado en uso actualmente. Pero el principio sigue en pie: una mejora sustancial en esta clase de algoritmos podría volver inseguras en el futuro ciertas longitudes de clave.

Implicaciones más amplias para la investigación científica

La hipótesis del tiempo exponencial se ha utilizado como punto de partida en un gran número de artículos de investigación durante la última década. Si la refutación es correcta, esos trabajos necesitarán una revisión, no solo en el nivel de los resultados, sino en el de los cimientos sobre los que se construyeron. Williams considera que todo investigador debería otorgar a la posibilidad de que P = NP algo más de peso que antes, aunque advierte de que lo publicado por los laboratorios «no es la respuesta definitiva» y que más adelante aparecerán algoritmos mejores.

Lo más importante es que este nuevo patrón de «descubrimiento científico asistido por inteligencia artificial» coloca a los investigadores ante una pregunta profesional directa: si buena parte de aquello en lo que solíamos trabajar se convierte en tareas sencillas para los modelos, ¿cómo elevamos el nivel de las preguntas que formulamos? La respuesta a esa pregunta puede ser más valiosa que cualquier demostración aislada.

✦ بقلم فريق دروب أيديا