Lance Fortnow lleva más de veinte años escribiendo sobre complejidad computacional y no es de los que se asombran fácilmente. Su post sobre la nueva afirmación terminaba con una frase cautelosa: "No he verificado la prueba yo mismo, pero ahora es seguro asumir que la hipótesis del tiempo exponencial está acabada" (Computational Complexity).
La afirmación viene de dos laboratorios. OpenAI, la empresa detrás de ChatGPT, dice que su modelo refutó la Hipótesis del Tiempo Exponencial, que normalmente se abrevia ETH. Horas después, Anthropic, creadora de Claude (aquí comparamos ambos asistentes), publicó su propia refutación. Los titulares enseguida vincularon la noticia con una pelea entre matemáticos y con el temor por el cifrado mundial. Leímos los textos de ambos laboratorios, los comentarios de expertos y la cobertura de prensa, y nuestra opinión es clara: el resultado probablemente sea real e importante para los teóricos, y no es motivo para cambiar cómo proteges tus datos. Dos de los tres titulares tratan de disputas distintas, y el tercero habla de una tendencia.
¿Qué es la Hipótesis del Tiempo Exponencial, en palabras sencillas?
Empecemos por un acertijo llamado 3-SAT. Te dan una larga lista de condiciones sobre n interruptores de verdadero o falso, cada una con la forma "A, o no B, o C", y tienes que encontrar una configuración de los interruptores que las cumpla todas. Comprobar una configuración propuesta es rápido. Encontrarla es lo difícil, como en un sudoku: un tablero resuelto se verifica fácil, uno en blanco no.
ETH, propuesta en 1999 por Russell Impagliazzo y Ramamohan Paturi (con Francis Zane), dice que todo algoritmo para 3-SAT necesita un tiempo que crece como 2 elevado a c por n, para alguna constante c mayor que cero (Fortnow). Imagina un candado de combinación en el que cada dial extra multiplica el trabajo por un factor fijo, digamos 1,3. ETH dice que ese factor se puede reducir, pero nunca hasta 1.
La refutación dice que el factor sí se acerca a 1 a medida que crecen las fórmulas. El paper de OpenAI da, según Fortnow, un tiempo de ejecución de aproximadamente 2 elevado a n por log log n dividido entre la raíz cuadrada de log n. Eso sigue estando lejos de ser rápido. Solo crece más despacio que cualquier multiplicador fijo. El texto de Anthropic lo dice sin rodeos: "El resultado es puramente asintótico y no dice nada sobre resolver fórmulas en la práctica" (Anthropic).
¿Por qué les importó tanto a los teóricos? ETH se había usado en cientos de papers como sustituto de "este problema no se puede resolver mucho más rápido" (OpenAI). Si la hipótesis es falsa, hay que volver a revisar esos argumentos de dificultad, aunque Fortnow señala que "el hecho de que ETH y SETH fallen no significa que sus implicaciones sean falsas".
Se ha verificado más de lo habitual, y menos de lo necesario para darlo por cerrado
La verificación hasta ahora es mayor que la que recibe la mayoría de los avances en su primera semana. OpenAI dice que su modelo encontró la refutación diez días antes del anuncio y que se formalizó en Lean, un verificador de pruebas que solo acepta pasos que puede comprobar (OpenAI). Anthropic dice que un modelo interno de Claude encontró su versión, y que sus archivos de Lean fueron escritos por modelos de IA (Anthropic).
Desde entonces se han sumado personas. Ryan O'Donnell, de Carnegie Mellon, publicó una exposición reescrita de la prueba, y Fortnow dice que Shiva Kintali publicó otra, ambas buscando la simplicidad por encima de las mejores cotas. Timothy Gowers dijo que era "muy sorprendente y de gran trascendencia que sea falsa" (Business Insider).
Quienes tienen el encargo formal de comprobarla son Impagliazzo, Paturi y Ryan Williams, del MIT, quien dijo a TechCrunch que partes de la prueba son rutinarias pero que "hay dos o tres partes de aspecto extraño". Business Insider informa de que Williams no ha certificado el resultado y de que el grupo aclara que su participación no es un respaldo. Una cautela más del propio repositorio de Anthropic: Lean comprueba las pruebas, pero "ninguna máquina comprueba que este archivo diga lo que dice el paper", así que una persona tiene que leer el breve archivo con los enunciados. Lo han mantenido corto precisamente por eso.
Nuestra lectura: una afirmación de dos laboratorios, con pruebas verificadas por máquina y reescrituras humanas en cuestión de días, es inusualmente sólida. Aun así, sigue siendo una afirmación hasta que el grupo de expertos y una revista digan otra cosa.
¿La pelea de los matemáticos es por este resultado?
En su mayor parte, no. La "pelea entre matemáticos" de la BBC trata de otro problema. Su reportaje cuenta la disputa sobre Navier-Stokes, donde Tristan Buckmaster, de NYU, preguntó si sus borradores, almacenados en la herramienta Codex de OpenAI, podrían haber alimentado el trabajo de la propia OpenAI. OpenAI respondió que nadie allí vio el trabajo del otro equipo y que sus prompts "no podrían haber influido en el sistema de ninguna manera".
El titular de Scientific American sobre haber "adelantado" a otros trata de Yang-Mills, un problema de física. La revista dice que OpenAI parece haberse adelantado a Ethan Sussman, que trabajaba con Levent Alpöge, de Anthropic, en una prueba. Alpöge protestó en X. Nada de eso tiene que ver con si el algoritmo de 3-SAT funciona.
La disputa sobre ETH es de proceso. Williams calificó una publicación anterior de OpenAI como "un ataque DDOS a los matemáticos" (X), y luego aceptó ayudar con esta. Scientific American afirma que el enfoque de OpenAI en dos de los tres resultados incumplió una declaración aclaratoria de su propio grupo asesor de expertos en IA y matemáticas, y que los prompts y la cadena de razonamiento detrás de ellos siguen siendo privados. En el caso de ETH, OpenAI sí aceptó publicar la prueba y financiar una conferencia.
¿Rompe RSA o el cifrado de mi teléfono?
No, y no por esta vía. Lo decimos tan categóricamente porque las razones son concretas. Primero, el algoritmo resuelve k-SAT. Fortnow subraya que "no aporta nada nuevo para Subset Sum o el Viajante de Comercio", porque convertirlos a 3-SAT infla demasiado el número de variables. Segundo, RSA se apoya en la dificultad de descomponer un número enorme en dos primos (el Financial Times describe el método sin nombrarlo), que es un problema distinto de satisfacer fórmulas lógicas, y ninguna de las fuentes que leímos dice que el nuevo algoritmo llegue hasta ahí. Tercero, la cota es asintótica: no cambia nada sobre una clave de 2.048 bits en ninguna máquina que exista.
Williams planteó la preocupación obvia a Dan Roberts, responsable científico de OpenAI. Según TechCrunch, le preguntó si algo era inseguro ahora, y transmitió que, al parecer, OpenAI lo había comprobado y estaba "razonablemente segura" de que no implicaba ninguna brecha. Es información de segunda mano y no publicada, así que pésala en consecuencia. Williams también dijo que un algoritmo mejorado podría implicar que algunos tamaños de clave se consideren rotos.
Debajo hay una pregunta abierta de verdad. Williams dice que "todo informático debería probablemente dar un poco más de peso a la plausibilidad de P = NP", pero John D. Cook señala que "el estatus de P = NP sigue siendo desconocido" (Business Insider). Williams tampoco cree que el nuevo algoritmo sea el mejor posible. Si llega uno más afilado, los argumentos cambian.
El artículo del Financial Times trata de una tendencia, no de esta prueba
El artículo del FT trata de la creciente capacidad matemática de la IA y del cifrado en general, y en el texto que pudimos leer nunca menciona ETH. Sus fuentes son mesuradas. El matemático australiano Geordie Williamson dijo ante un público de Imperial College que la IA está provocando "una especie de reestructuración completa de lo que es la dificultad", y que debemos esperar sacudidas. Daniel Shiu, de la Universidad de Mánchester, calificó de "riesgo significativo" que la IA rompa el cifrado para las "formas más matemáticas de criptografía", y citó algunos de los algoritmos resistentes a la computación cuántica "menos maduros". El propio FT dice que la IA "aún no ha roto ningún método criptográfico fundamental".
Scott Aaronson añadió un cabo suelto: la criptografía brilla por su ausencia en la lista anterior de 376 papers de OpenAI, y en una actualización de su post escribió que sus fuentes dicen que las empresas de IA han empezado a investigar si sus modelos pueden romper protocolos. No dio nombres, y nosotros tampoco podemos.
Nuestra lectura: la preocupación razonable se refiere a los esquemas más nuevos, no a los de tu navegador. Los estándares de NIST de 2024 incluyen dos esquemas basados en retículos y un tercer estándar de firma construido sobre un tipo distinto de matemáticas, que se mantiene como respaldo por si el primero resulta vulnerable.
Qué debería hacer realmente una pequeña empresa
Casi nada, y nada urgente. El árbol de abajo ordena las tres situaciones que consideramos relevantes.
Hay un hábito que vale la pena adoptar con independencia de esta noticia. El regulador del Reino Unido dijo al FT que "las empresas no deberían esperar para actuar" a la hora de prepararse ante los riesgos de la IA y la computación cuántica para la criptografía, y BT dijo que quiere que su criptografía se "cambie con más facilidad a medida que evolucionen los estándares, las tecnologías y las amenazas". Para un negocio pequeño, eso se traduce en mantener el software actualizado y preguntar a los proveedores cómo cambiarían de algoritmo. Nuestro marco para confiar tus datos a herramientas de IA cubre las preguntas que hacer a los proveedores, y el panel de Seguridad y Privacidad de ToolRank lista las herramientas por categoría.
Tres cosas que vigilar antes de que alguien diga que está cerrado
Vigila tres cosas. El informe del grupo de expertos formado por Impagliazzo, Paturi y Williams, y la conferencia que OpenAI aceptó financiar. Lecturas independientes de los archivos con los enunciados en Lean, porque ahí es donde podría esconderse un error sutil. Y la revisión por pares en una revista, de la que todavía no hemos encontrado señales. Hasta que aparezca lo primero, diríamos "muy probablemente refutada".