La IA refuta la hipótesis del tiempo exponencial: qué significa todo esto

OpenAI y Anthropic han publicado cada una una prueba de que la hipótesis del tiempo exponencial es falsa.

ETH es una suposición de 27 años en la informática teórica que sostiene que ciertos problemas no pueden resolverse mucho más rápido que por fuerza bruta. Ahora, los principales laboratorios de IA dicen que eso, sencillamente, no es cierto.

Si las pruebas se sostienen, serían el resultado generado por IA más importante en informática hasta la fecha. También obligan a replantear literalmente cientos de artículos de investigación que asumían que ETH era cierta.

En este artículo explicamos qué significa realmente la hipótesis del tiempo exponencial y cómo se relaciona con P vs. NP. También veremos qué afirman exactamente ambos laboratorios, cómo se comprobaron las pruebas y qué cambia (y qué no) para la criptografía.

P vs. NP en términos sencillos

P frente a NP pregunta si todo problema cuya respuesta es fácil de comprobar también es fácil de resolver. Es uno de los siete Problemas del Milenio y sigue abierto tras esta noticia.

El Sudoku es el ejemplo clásico. Comprobar una cuadrícula rellena lleva segundos: basta con revisar si se repiten números en cada fila, columna y subcuadrícula. Encontrar la solución a partir de una cuadrícula casi en blanco puede llevar mucho más tiempo, y la diferencia explota a medida que crece el tamaño.

• P es la clase de problemas que un ordenador puede resolver en tiempo polinómico, es decir, cuyo trabajo crece como n², n³, etc., según crece el tamaño de entrada n.
• NP es la clase de problemas cuyas soluciones propuestas un ordenador puede verificar en tiempo polinómico.

Todo problema en P está también en NP. La cuestión abierta es si ocurre lo contrario. La mayoría de informáticos creen que P ≠ NP, de modo que algunos problemas son, en esencia, más difíciles de resolver que de comprobar. La criptografía moderna se apoya en esa creencia: cifrar es fácil, pero deshacer el cifrado sin la clave debería ser difícil.

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

ETH va más al detalle: afirma que un problema concreto de NP, 3-SAT, necesita tiempo exponencial por muy ingenioso que sea el algoritmo. Russell Impagliazzo y Ramamohan Paturi, de la Universidad de California en San Diego, la propusieron a finales de los 90, con Francis Zane contribuyendo al trabajo fundacional.

El problema 3-SAT

En 3-SAT, recibes una fórmula compuesta por n variables verdadero/falso y una lista de cláusulas. Cada cláusula une tres condiciones con OR, por ejemplo «x₁ es verdadera O x₄ es falsa O x₇ es verdadera». La tarea es encontrar una asignación de las variables que satisfaga todas las cláusulas a la vez.

La fuerza bruta prueba las 2ⁿ asignaciones, así que cada variable adicional duplica el trabajo. Se ve que con alrededor de 100 variables eso es inviable.

Lo que afirma ETH

ETH establece que existe una constante c > 1 tal que ningún algoritmo resuelve 3-SAT más rápido que cⁿ. Los algoritmos ingeniosos pueden reducir la base por debajo de 2, pero nunca hasta algo subexponencial. Formalmente: existe δ > 0 tal que 3-SAT no puede resolverse en tiempo O(2^δn).

Durante décadas, el progreso cuadró con ese panorama. Los investigadores fueron rebajando la base, pero se mantuvo muy por encima de 1. Como 3-SAT puede transformarse en muchos otros problemas, ETH se convirtió en una suposición de trabajo. Se usó para argumentar que problemas como Clique, Vertex Cover, Independent Set y otros tampoco podían resolverse mucho más rápido. 

Cómo se compara el nuevo resultado

La nueva cota se escribe en abreviatura 2^o(n). El coste por variable añadida tiende a 1 a medida que crece n, que es justo lo que ETH decía que era imposible.

Qué anunciaron OpenAI y Anthropic

Ambos laboratorios alcanzaron esencialmente la misma cota subexponencial de forma independiente, y ambos respaldaron sus artículos con pruebas verificadas por máquina en el asistente de pruebas Lean.

Anthropic afirma que Claude encontró el algoritmo central sin intervención humana tras producir unos 14 millones de tokens de salida. Su método usa redes tensoriales y argumentos de rango. Investigadores humanos ayudaron después con el artículo final.

¿Por qué ambos laboratorios lo encontraron el mismo día?

Ninguno ha explicado el momento. El artículo de Anthropic califica ambos resultados de independientes y simultáneos, y los dos textos siguen rutas matemáticas distintas para llegar esencialmente a la misma cota. 

Con algo de contexto, el solapamiento sorprende menos de lo que parece. Ambos laboratorios han estado apuntando sus modelos a largas listas de problemas abiertos, y OpenAI en solitario publicó cientos de manuscritos de matemáticas generados por IA a principios de octubre. ETH es uno de los objetivos más conocidos del área, y ambos modelos aprendieron de la misma investigación publicada. El descubrimiento independiente y simultáneo también es un patrón antiguo en ciencia, como con Newton y Leibniz en el cálculo o Darwin y Wallace en la selección natural.

¿Qué solidez tienen las pruebas?

Lean confirma que una afirmación formal se sigue lógicamente de sus axiomas. No puede confirmar que la afirmación formal diga lo mismo que el artículo. Anthropic señala que ninguna máquina comprueba esa equivalencia, y OpenAI dice que su archivo de Lean demuestra una cota ligeramente más débil que su titular.

Ahora, los mismos investigadores que propusieron el problema, Impagliazzo y Paturi, junto con Ryan Williams del MIT, están organizando talleres para evaluar si las afirmaciones formales capturan realmente ETH. Su carta recalca que participar en la revisión no implica respaldo. A día de hoy, cuando se escribe este artículo, nadie ha encontrado públicamente un fallo. 

Williams ha dicho que partes de la prueba de OpenAI parecen rutinarias, mientras que «dos o tres partes con pinta de alienígena» aún necesitan escrutinio. Impagliazzo, uno de los autores de ETH, ha descrito el resultado como profundamente sorprendente.

Qué cambia y qué no

En la práctica, hoy no cambia casi nada (menos mal): los nuevos algoritmos solo superan a la fuerza bruta en entradas mucho mayores que cualquier cosa que un ordenador pueda albergar.

No habrá SAT solvers más rápidos

El artículo de Anthropic dice que su método solo vence a la fuerza bruta con entradas astronómicamente grandes. Para fórmulas típicas con cinco cláusulas por variable, el punto de cruce es un número con unas 10.000 cifras. En el caso más general, es un número con aproximadamente 100 millones de cifras. 

Los autores también afirman que su enfoque difícilmente ayudará con menos de unos 10 millones de variables. Los SAT solvers usados en verificación de chips, planificación u optimización no se acelerarán gracias a este resultado.

La criptografía no está rota

El resultado no toca P vs NP. Nadie pretende lo contrario. OpenAI dice que comprobó si el algoritmo rompe criptosistemas reales y está bastante segura de que no lo hace. 

La teoría se reescribe

El mayor impacto está en la investigación. Los resultados de dureza basados en ETH o SETH ahora necesitan un nuevo apoyo, y algunos investigadores han dicho que años de su propio trabajo podrían requerir revisión. No todo se viene abajo, eso sí. Anthropic señala que el resultado no refuta el problema de los vectores ortogonales, que sustenta muchos resultados de complejidad de grano fino. 

Por qué importa para la IA

El titular va menos de 3-SAT y más de quién encontró la respuesta: dos sistemas de IA tumbaron de forma independiente una conjetura en la que expertos humanos confiaron durante una generación.

IA como colaboradora de investigación

Los investigadores describen ahora resultados nuevos de IA que llegan cada semana o dos, trastocando proyectos en curso. Herramientas formales como Lean se vuelven centrales porque permiten confiar en una prueba larga escrita por máquina sin rederivar cada línea.

Atajos ocultos y auto-mejora

ETH recogía la creencia de que algunos problemas de búsqueda no tienen atajo ingenioso. Si esa creencia es errónea, otros problemas obviamente difíciles podrían ocultar atajos también.

Pienso en el descubrimiento de algoritmos como un área donde esos atajos podrían importar mucho para la auto-mejora recursiva, la idea de sistemas de IA que ayudan a diseñar mejores IA. Usar IA para encontrar algoritmos más rápidos es una vía concreta hacia ello, aunque nada en este resultado lo logre directamente hoy.

Qué significa para quienes trabajan con datos

Para quienes construyen con datos, destacan tres lecciones:

• La teoría de la complejidad no es solo académica: Saber por qué un problema es NP-difícil te dice cuándo pensar en heurísticas, aproximaciones o solvers en lugar de búsqueda exacta.
• Verificar es una habilidad: A medida que la IA genera más código y análisis, comprobar su salida (con tests, pruebas formales o flujos reproducibles) importa tanto como producirla.
• Las asíntotas pueden engañar: Un algoritmo «más rápido» en teoría puede ser inútil en tamaños del mundo real. 

Conclusión

Si las pruebas superan la revisión de expertos, la hipótesis del tiempo exponencial se unirá a la corta lista de conjeturas muy aceptadas que resultaron falsas (como la conjetura de la suma de potencias de Euler). Pero P vs NP sigue abierta y la criptografía, por ahora, está a salvo.

Los próximos hitos a vigilar son los talleres de revisión liderados por los autores originales de ETH, las reimplementaciones independientes de los algoritmos y si alguien ajusta aún más la cota.

Para construir las bases detrás de historias como esta, explora nuestros cursos de estructuras de datos y algoritmos, programación en Python y machine learning. Cubren el pensamiento de Big-O que hace que resultados como este sean comprensibles.