La hipótesis del tiempo exponencial y el problema 3-SAT acaban de recibir el mismo golpe desde dos casas rivales. OpenAI anunció el 26 de octubre que un modelo interno refutó esa conjetura, y horas después Anthropic publicó una refutación propia, firmada por Claude. El dato que deja fría a la comunidad: ambos fechan el hallazgo el mismo día, el 16 de octubre de 2026, sin saber del trabajo del otro.
Si las dos demostraciones superan la revisión independiente que ya arrancó, más de 800 estudios quedan con su base formal en entredicho. Nada está confirmado: son los reclamos de los dos laboratorios, con las demostraciones abiertas a revisión.
Una conjetura de 1999 que sostenía cientos de estudios
Russell Impagliazzo y Ramamohan Paturi, de la Universidad de California en San Diego, plantearon la hipótesis en 1999, y Francis Zane se sumó a la formalización en 2001. Su pieza central, el problema 3-SAT, es una fórmula lógica de variables que valen verdadero o falso, agrupadas en cláusulas de tres condiciones: resolverlo es hallar una combinación que las cumpla todas a la vez.
Ningún algoritmo, afirma la conjetura, puede resolver 3-SAT en tiempo subexponencial, es decir, creciendo más despacio que una exponencial sobre el número de variables. En palabras llanas: probar combinaciones una por una sería insuperable. Durante 27 años, investigadores de teoría de grafos, biología computacional y criptografía usaron esa idea para declarar duros sus propios problemas, sin resolver la pregunta mayor de P frente a NP.
Ese andamiaje es lo que entra en revisión. El conteo de Anthropic localizó 800 estudios apoyados en la hipótesis del tiempo exponencial o en otra que la implica. Que la base caiga no vuelve fáciles esos problemas; obliga a cada campo a buscar otro fundamento.
El mismo resultado, dos laboratorios y un solo día
OpenAI contó que su sistema produjo la refutación en lenguaje natural el 16 de octubre y la formalizó en Lean al día siguiente. Lean es un asistente de demostraciones que comprueba, paso a paso, que cada deducción se sigue de las premisas declaradas. Texto y código quedaron públicos en el GitHub de la empresa, con revisión del manuscrito del 25 de octubre.
El algoritmo atribuido al modelo es determinista, sin azar, y hace una tarea más exigente que decidir si existe una solución: cuenta exactamente cuántas asignaciones cumplen una fórmula, en tiempo subexponencial y con espacio polinómico. Contar es más difícil que decidir, así que ese algoritmo también resuelve el problema original.
Anthropic movió ficha la noche del 27 de octubre con un artículo titulado «A 2^o(n) Time Algorithm for 3-SAT», acreditado a Claude. Su nota de procedencia dice que el algoritmo central lo encontró el 16 de octubre un modelo interno, con 14 millones de tokens de salida y sin intervención humana. El matemático Jelani Nelson observó que ambas demostraciones llegan a una cota de tiempo muy parecida, señal de técnicas cercanas pese a la independencia declarada.
Su versión añade dos piezas: también refuta la variante fuerte de la misma hipótesis, más estricta, y trae algoritmos teóricos más rápidos para conjunto independiente, clique, cobertura de vértices y conjunto dominante.
OpenAI sumó dos reclamos más en el mismo anuncio
El anuncio del 26 de octubre trajo otros dos resultados del mismo modelo interno. Uno afirma demostrar la conjetura de suavizado local de Christopher Sogge, de 1991, en todas las dimensiones, lo que arrastraría la conjetura de Kakeya y la de restricción de Stein. La comunidad humana solo había cerrado Kakeya en tres dimensiones, en 2025.
Otro reclamo apunta a la física: una demostración rigurosa de existencia para ciertas teorías cuánticas de campos en cuatro dimensiones, entre ellas la cromodinámica cuántica y la teoría pura de Yang-Mills, pieza de uno de los Problemas del Milenio del Instituto Clay. Ese material quedó en manos de un grupo del Nobel David Gross, que redactará la versión definitiva sin publicar los textos de la máquina.
Qué comprueba Lean y qué queda por comprobar
Lean verifica la coherencia lógica interna de una demostración formal. Lo que no puede garantizar es que la formalización traduzca con fidelidad el argumento en lenguaje natural: ya hay formalizaciones que compilan bien y dicen otra cosa. Anthropic reforzó su archivo con nanoda, un segundo núcleo escrito en Rust por otro equipo, y aun así admite que su formalización la escribió la IA y la revisaron otros modelos iguales.
La revisión humana quedó en manos llamativas: Impagliazzo y Paturi, dos de los tres autores de la conjetura, junto a Ryan Williams, del Instituto Tecnológico de Massachusetts (MIT). Los tres publicaron una carta abierta con una advertencia directa: su participación no debe tomarse como certificación del reclamo. El grupo trabaja sin pago ni acuerdos de confidencialidad, y OpenAI aceptó liberar los datos brutos y financiar una conferencia sobre el resultado. La empresa aportó además US$5 millones a la Fundación Simons para talleres sobre matemáticas de IA.
El punto de cruce que fija el artículo de Anthropic merece frialdad: unas 10^10.000 variables. Solo con fórmulas de ese tamaño el algoritmo nuevo supera a la fuerza bruta, impracticable ya cerca de las 100 variables. El resultado no dice nada sobre resolver fórmulas en la práctica, y tampoco acerca la respuesta a P frente a NP; el presidente de OpenAI declaró que P probablemente sigue sin ser igual a NP. El primer veredicto con autoridad será el del panel revisor.
Fuente: TechTimes
Foto: Solen Feyissa vía TechTimes
Descubre más desde Tecnología Geek
Suscríbete y recibe las últimas entradas en tu correo electrónico.
