Intensivo Gratis 21–22.11Intensivo gratuito de 2 días en Vibecoding (21–22 nov, 16:00 MSK) · Cohorte 3 inicia 23.11Registrarse gratis →Cohorte 3 (23.11)

OpenAI afirma que su IA refutó una hipótesis de 1999 sobre la velocidad para resolver problemas complejos

OpenAI afirma que su modelo encontró un algoritmo para problemas complejos como el sudoku, los horarios y el viajante de comercio, que contradice la hipótesis del tiempo exponencial (ETH) de 1999. Esa hipótesis sostenía que, con cada nueva variable, el tiempo de resolución en el peor caso se duplica, mientras que el algoritmo de OpenAI crece más lentamente. La demostración en formato Lean está en GitHub y cualquiera puede comprobarla. Por ahora, es solo una afirmación de la compañía: tu planificador no será más rápido.

Procesado por IA desde TG: @hiaimedia (Hi, AI • Новости технологий); editado por Hamidun News
OpenAI afirma que su IA refutó una hipótesis de 1999 sobre la velocidad para resolver problemas complejos
Fuente: TG: @hiaimedia (Hi, AI • Новости технологий). Collage: Hamidun News.
Escuchar artículo
Ficha técnica y cifras clave
ParámetroDatos
Fuente originalTG: @hiaimedia (Hi, AI • Новости технологий) ↗
Editor jefe
Dato clave #1La verificación la dirigirán Ryan Williams, del MIT, y dos autores de la ETH.
Dato clave #2La ETH sustenta cientos de trabajos sobre grafos, biología y bases de datos.
Dato clave #3A principios de octubre, tres de los 722 artículos de OpenAI se retiraron por un error.

Imagina que escribes un planificador de turnos para un almacén o un enrutador para repartidores. Cuantos más pedidos y condiciones hay, más lento funciona el programa, y en algún momento simplemente no llega a tiempo. La informática se pregunta desde hace tiempo si esto es un defecto de nuestros algoritmos o un límite de la propia tarea. OpenAI afirma que su modelo interno encontró un algoritmo que refuta una de las principales hipótesis sobre el tema. Por ahora, es solo una afirmación, así que a continuación analizamos qué ya está claro y qué no.

De qué trata la disputa y qué tiene que ver el sudoku

La hipótesis del tiempo exponencial (ETH) surgió en 1999. Se refiere a una amplia clase de problemas combinatorios en los que la solución es fácil de comprobar, pero difícil de encontrar. El sudoku es un buen ejemplo: verificar que los números están bien colocados lleva un minuto. Resolver un tablero así de rápido es mucho más complicado, sobre todo si crece de 9×9 a 1000×1000. A esta misma clase pertenecen la elaboración de horarios, el problema del viajante de comercio y miles de otras tareas de logística, planificación y optimización.

Si se prueban las opciones una por una, el tiempo máximo de ejecución se duplica con cada nueva variable. Por ejemplo: si 50 condiciones requieren una hora, 51 necesitarán dos, y 52, cuatro. Existen métodos más sofisticados que funcionan algo más rápido. Pero la ETH sostenía que, en el peor caso, el tiempo seguiría creciendo exponencialmente. Según OpenAI, el algoritmo que encontró su modelo crece más lentamente que cualquier exponencial. Eso es precisamente lo que contradice la hipótesis.

Cómo se va a verificar

La demostración está escrita en el lenguaje Lean y publicada en GitHub. Lean es un sistema de verificación formal: comprueba mediante una máquina cada paso del razonamiento, por lo que no hace falta confiar en la palabra del autor. Cualquier persona puede ejecutar la comprobación en su propio equipo. El grupo de revisión lo dirigirán el profesor del MIT Ryan Williams y dos autores de la propia hipótesis, Russell Impagliazzo y Ramamohan Paturi. Es decir, el resultado lo evaluarán quienes mejor entienden qué debería refutarse.

La cautela se entiende. A principios de octubre, OpenAI publicó 722 artículos sobre problemas matemáticos no resueltos. Menos de un día después, tres trabajos tuvieron que retirarse por un error. Parte de los matemáticos criticó este enfoque. El medallista Fields Terence Tao calificó de «residuos tóxicos» las demostraciones que las empresas de IA producen en masa en la carrera por los benchmarks. En este contexto, el nuevo trabajo, con su formalización, parece bastante más serio, pero hay que esperar a la confirmación.

Qué cambia para los profesionales

La ETH sustenta cientos de trabajos en teoría de grafos, biología computacional y bases de datos. Muchos de ellos demuestran que ciertos problemas no pueden resolverse más rápido que un determinado umbral. Si la refutación se confirma, esas conclusiones perderán su base, y los teóricos tendrán que revisar parte de sus resultados.

Pero no conviene exagerar el efecto. De la refutación de la ETH no se deducen por sí mismos algoritmos rápidos para esos problemas; habrá que buscarlos por separado. Por eso, los desarrolladores de planificadores, solvers y optimizadores no tienen motivo para reescribir su código hoy: tu búsqueda de horarios no será más rápida.

De esta historia se pueden extraer dos lecciones prácticas:

  • Si una IA produce un resultado complejo, ya sea una demostración o código, lo más importante es si puede verificarse mediante una máquina. Un formato como Lean convierte «suena convincente» en «está comprobado».
  • Generar se ha vuelto barato, pero verificar sigue siendo caro. Las tres obras retiradas en un solo día muestran que el cuello de botella no será el modelo, sino el equipo que revisa sus conclusiones.

Si Williams, Impagliazzo y Paturi encuentran un fallo en la demostración, la historia terminará con otra retirada. Si no lo encuentran, la IA habrá refutado por primera vez una hipótesis sobre la que se construyeron cientos de trabajos de teoría de la complejidad.

Historia

Preguntas frecuentes sobre la noticia

¿Qué se sabe sobre De qué trata la disputa y qué tiene que ver el sudoku?

La hipótesis del tiempo exponencial (ETH) surgió en 1999. Se refiere a una amplia clase de problemas combinatorios en los que la solución es fácil de comprobar, pero difícil de encontrar. El sudoku es un buen ejemplo: verificar que los números están bien colocados lleva un minuto. Resolver un tablero así de rápido es mucho más complicado, sobre todo si crece de 9×9 a 1000×1000.

Cómo se va a verificar?

La demostración está escrita en el lenguaje Lean y publicada en GitHub. Lean es un sistema de verificación formal: comprueba mediante una máquina cada paso del razonamiento, por lo que no hace falta confiar en la palabra del autor. Cualquier persona puede ejecutar la comprobación en su propio equipo. El grupo de revisión lo dirigirán el profesor del MIT Ryan Williams y dos autores de la propia hipótesis, Russell Impagliazzo y Ramamohan Paturi.

¿Qué se sabe sobre Qué cambia para los profesionales?

La ETH sustenta cientos de trabajos en teoría de grafos, biología computacional y bases de datos. Muchos de ellos demuestran que ciertos problemas no pueden resolverse más rápido que un determinado umbral. Si la refutación se confirma, esas conclusiones perderán su base, y los teóricos tendrán que revisar parte de sus resultados. Pero no conviene exagerar el efecto. De la refutación de la ETH no se deducen por sí mismos algoritmos rápidos para esos problemas; habrá que buscarlos por separado.

ZK
Zhemal Khamidun — CPO de Alpina Digital, product manager de AlpinaGPT. Crea productos de IA desde 2019. Hamidun News es un proyecto personal que creció hasta ser un agregador en producción con más de 6.000 lectores.
✦ Unified AI Workspace · Nomad

Test Frontier LLMs & Autonomous Agents in One Workspace

Run Claude Opus 5.5, GPT-6, Gemini 3.1, and DeepSeek side-by-side in Nomad AI (nomadnet.ai) — unified model routing, deep research, and multimodal workflows under one subscription.

Try Nomad AI →Launch Nomad Agent
¿Qué te parece?
Cargando comentarios…