OpenAI dice refutar la ETH: qué cambia en computación

Qué pasó: OpenAI dice haber refutado la ETH

OpenAI publicó soluciones a tres problemas matemáticos que llevaban décadas sin resolverse. Una de ellas es un rechazo inesperado a la hipótesis del tiempo exponencial (ETH), una suposición de la informática teórica que sostiene buena parte de lo que creemos saber sobre qué es difícil de computar.

Según The Next Web, la compañía afirmó que un modelo interno encontró la refutación el 16 de octubre y que el resultado se verificó al día siguiente en Lean, un lenguaje que comprueba demostraciones de forma mecánica. El manuscrito y la prueba formalizada quedaron publicados en GitHub. Decrypt precisa que se trata de un paper de 67 páginas, fechado el 17 de octubre y revisado el 25.

Como en anteriores entregas de demostraciones de los laboratorios frontera, la reacción de la comunidad científica mezcló entusiasmo y malestar. El matemático de Anthropic Levent Alpöge sugirió que OpenAI se basaba en trabajo preexistente y, horas después, Anthropic publicó su propia refutación de la ETH: un paper acreditado a Claude titulado A 2^o(n) Time Algorithm for 3-SAT, según Decrypt.

¿Qué es la hipótesis del tiempo exponencial y por qué importa?

La ETH es una conjetura de 1999, propuesta por Russell Impagliazzo y Ramamohan Paturi, de UC San Diego, junto con Francis Zane. Dice, en términos simples, que incluso el algoritmo más rápido necesita tiempo exponencialmente mayor para encontrar una solución a medida que crecen las variables de cierto tipo de problema lógico.

Ese problema es SAT (satisfacibilidad booleana): determinar si un conjunto de condiciones lógicas puede cumplirse a la vez. OpenAI sostiene que su modelo encontró un algoritmo determinista que cuenta las soluciones en tiempo subexponencial, es decir, más rápido de lo que se creía posible.

La relevancia no es abstracta. Según The Next Web, cientos de papers de informática usan la ETH para demostrar que problemas de teoría de grafos, biología computacional, bases de datos y geometría computacional no se pueden resolver rápido. Si la refutación se sostiene, esos resultados condicionales tendrían que revisarse.

El problema P vs NP, explicado sin fórmulas

La ETH forma parte de una familia más amplia conocida como P vs NP, que anima la informática desde hace décadas. La pregunta de fondo: ¿todo problema cuya solución se puede verificar fácilmente también se puede resolver fácilmente?

Ryan Williams, profesor del MIT que organiza la respuesta del campo, lo ilustró con el Sudoku: una vez que la solución está puesta, se verifica en segundos, pero encontrarla lleva tiempo. Esa asimetría sostiene los sistemas criptográficos: con la clave, descifras; sin ella, romper el código lleva demasiado tiempo para ser útil.

"P = NP afirma que esto es cierto para cada problema que puedes verificar rápido", dijo Williams a TechCrunch. "Parece demasiado bueno para ser verdad". Por eso la mayoría de los científicos asume que P ≠ NP, y la ETH aportaba evidencia en ese sentido.

Williams fue cuidadoso con el alcance del hallazgo: "Creo que cuestiona muchas de las intuiciones que teníamos sobre cuán tratables son los problemas NP difíciles. También creo que probablemente no sea la respuesta final".

Anthropic responde y la comunidad pide cuentas

El proceso de OpenAI cambió esta vez. La compañía estructuró la entrega de forma distinta para cada disciplina, según TechCrunch: los matemáticos recibieron el trabajo en GitHub; los informáticos formaron un grupo de trabajo que pidió publicar las pruebas y que OpenAI financiara una conferencia; los físicos armaron un grupo que decidirá cómo se libera su resultado.

Williams, que en el pasado calificó una entrega previa de OpenAI como un "ataque DDOS contra los matemáticos", aceptó colaborar. El laboratorio le pidió ayuda para interpretar la solución junto a Impagliazzo y Paturi, los autores originales de la ETH.

Su primer paso fue una carta abierta para pedir retroalimentación y discutir las normas sobre contribuciones de IA al trabajo científico. "Nuestra participación no debe tomarse como certificación de la afirmación", escribieron los tres, según The Next Web. También señalaron que no firmaron acuerdos de confidencialidad y que no cobran. OpenAI aceptó liberar los datos crudos y financiar la conferencia.

Williams describió el contenido con honestidad: "Algunas partes son, digamos, rutinarias, pero hay dos o tres partes de aspecto alienígena, y son exactamente esas las que me hicieron pensar que toda la comunidad necesita trabajar en esto junta".

No es un caso aislado. En octubre, TechCrunch reportó que las soluciones matemáticas de OpenAI no cumplían los estándares del campo: solo 10 de 719 manuscritos incluían la cadena de razonamiento del modelo. El matemático Terence Tao advirtió entonces que hay problemas "resueltos de forma autónoma por prompters de IA que no tienen interés en el campo más amplio".

¿Qué significa esto para tu startup?

Primero, calma con el titular fácil: refutar la ETH no rompe la criptografía que usas hoy. Williams contó que su primera pregunta al líder científico de OpenAI, Dan Roberts, fue si el resultado afectaba algún sistema criptográfico. La respuesta, según él, fue que lo revisaron y están razonablemente seguros de que no implica ninguna ruptura.

Segundo, el paper mismo aclara que el resultado no demuestra que todo problema NP se resuelva en tiempo subexponencial, así que P vs NP sigue abierto. Y TechCrunch lo subraya: una cota teórica más rápida no es lo mismo que una mejora práctica inmediata.

Lo accionable está en otro lado:

• No cambies tu stack de seguridad por este anuncio. Si tu producto depende de RSA, ECC o cualquier primitiva estándar, la recomendación sigue siendo la misma: mantener librerías actualizadas, planificar migración a criptografía post-cuántica según los plazos de tu sector y no reaccionar a titulares de investigación teórica.
• Trata los resultados de IA como datos crudos, no como conclusiones. OpenAI mismo describe los manuscritos como material que necesita convertirse en entendimiento científico. Si tu equipo usa modelos para investigación, documenta qué generó el modelo, qué verificó un humano y con qué herramienta. Lean verifica que una afirmación se sigue de sus supuestos, pero no que esos supuestos correspondan al problema original.
• Vigila el costo de verificación, no solo el de generación. Cuando un modelo produce resultados a escala, el cuello de botella se mueve a revisarlos. Presupuesta tiempo de revisión humana proporcional al impacto de la decisión, igual que harías con cualquier output crítico.

Conclusión

El episodio deja una lección de gestión más que de matemáticas: cuando una herramienta produce resultados extraordinarios, el valor no está en el anuncio sino en el proceso que los verifica. OpenAI cambió su método, aceptó liberar datos y financiar la discusión pública. Williams, aun con reservas, se mostró optimista: la IA, dijo, "está forzando a la gente a ser un poco más ambiciosa sobre el tipo de trabajo que hace".

Para un founder, la traducción es directa: adopta la capacidad, pero construye el proceso de verificación antes de confiar en el resultado.

Fuentes

• TechCrunch: Frontier AI labs say their models refuted the Exponential Time Hypothesis (fuente original)
• The Next Web: OpenAI says its AI model has disproved the Exponential Time Hypothesis
• Decrypt: OpenAI Proves ETH Is False, and Crypto Twitter Has Questions
• Unite.AI: OpenAI Says Its Models Produced Three Proofs in Math, CS, and Physics
• TechCrunch: OpenAI's math solutions aren't meeting the field's standards yet