Hipótesis del tiempo exponencial (ETH)

Algunos problemas solo sabemos resolverlos probando casi todas las posibilidades. La hipótesis del tiempo exponencial, en inglés Exponential Time Hypothesis y abreviada ETH, es la apuesta de los informáticos de que, para un problema concreto, no habrá otra forma de hacerlo por muy listos que seamos. Existen métodos más rápidos, pero incluso los mejores necesitarán un número de pasos que crece exponencialmente con el tamaño del problema.

La ETH está muy relacionada con el problema P frente a NP, al que dedicamos un artículo aparte. Si no lo has leído, échale un vistazo primero, porque vamos a construir sobre él. Sobre todo sobre qué es la complejidad de un algoritmo y por qué hay un abismo tan grande entre n² y 2ⁿ.

A quién invitar a la fiesta

Estás preparando una fiesta y quieres invitar a cuatro amigos: Tomás, Javier, Karina y Diego. El problema es que entre ellos hay relaciones de todo tipo y te gustaría que todos estuvieran a gusto. Después de mucho preguntar, te salen seis condiciones:

1. Viene Tomás o Karina (o los dos).
2. Javier y Karina no se soportan, así que no vienen los dos.
3. Diego solo viene si también viene Javier.
4. Si viene Tomás, tiene que venir también Karina o Diego.
5. Si vienen Tomás y Karina, tiene que venir también Javier.
6. Viene al menos uno de los tres: Tomás, Javier o Diego.

¿A quién invitas para que se cumplan todas las condiciones a la vez? Intenta averiguarlo tú; la solución está al final del artículo.

Un informático reescribiría el problema en el lenguaje de la lógica proposicional. Cada amigo recibe una letra, por ejemplo T de Tomás. Cada letra es verdadera (Tomás viene) o falsa (Tomás no viene). El símbolo ∨ se lee «o» y ¬ se lee «no». La primera condición queda así:

$$T\vee K$$

La segunda condición dice que no viene Javier o no viene Karina:

$$\mathrm{\neg }J\vee \mathrm{\neg }K$$

Con la tercera condición es fácil equivocarse. «Diego solo viene si también viene Javier» significa que no puede pasar que Diego venga y Javier no. Es decir, o Diego no viene, o viene Javier:

$$\mathrm{\neg }D\vee J$$

Del mismo modo reescribimos el resto. El problema completo queda así:

$$\begin{array}{rcl}1.& & T\vee K\\ 2.& & \mathrm{\neg }J\vee \mathrm{\neg }K\\ 3.& & \mathrm{\neg }D\vee J\\ 4.& & \mathrm{\neg }T\vee K\vee D\\ 5.& & \mathrm{\neg }T\vee \mathrm{\neg }K\vee J\\ 6.& & T\vee J\vee D\end{array}$$

Fíjate en lo parecidas que son las condiciones: unas cuantas letras, algunas con el signo ¬, unidas por la palabra «o». Y ninguna tiene más de tres letras. El problema en el que tenemos condiciones así y buscamos cómo asignar a las letras verdadero y falso para que se cumplan todas a la vez se llama 3-SAT. El tres indica que cada condición tiene como mucho tres letras, y SAT es la abreviatura del inglés satisfiability, satisfacibilidad.

A primera vista parece un pasatiempo de revista. Sin embargo, una cantidad enorme de problemas prácticos se puede reescribir en forma de 3-SAT: horarios de clases, la comprobación de que un chip de un procesador calcula correctamente, la planificación de turnos e incluso el sudoku. Entonces no hay cuatro letras, sino que puede haber millones.

¿Cuántas posibilidades hay que probar?

El método más directo es probarlo todo. Tomás viene o no viene: son dos posibilidades. Para cada una de ellas, Javier viene o no viene: ya son cuatro posibilidades. Para cuatro amigos hay

$$2\cdot 2\cdot 2\cdot 2=2^4=16.$$

Es el mismo razonamiento que hicimos con los vectores binarios en el artículo sobre P frente a NP. Si tenemos n letras, podemos asignarles verdadero y falso de 2ⁿ maneras. Para 4 amigos son 16 posibilidades, que repasas en un par de minutos. Para 100 letras son

$$2^{100}\approx 1,27\cdot {10}^{30}$$

posibilidades. Si un ordenador probara mil millones de posibilidades por segundo, necesitaría unas tres mil veces más tiempo del que lleva existiendo el universo.

Pero al revés es fácil: si alguien te dice «invita a estos tres», lo compruebas al momento. Basta con repasar las seis condiciones y mirar si se cumple cada una. Encontrar la solución es difícil, comprobarla es fácil. Precisamente este tipo de problemas son los que en el artículo sobre P frente a NP colocamos en la clase NP.

Pero 3-SAT no es un problema cualquiera de NP: en 1971 se demostró que cualquier problema de NP se puede traducir a 3-SAT. Así que quien resolviera 3-SAT rápidamente resolvería rápidamente absolutamente todo lo que se puede comprobar rápido. Los problemas con esta propiedad se llaman NP-completos, y 3-SAT es su representante más famoso.

¿Se puede más rápido que 2ⁿ?

Sí. Probarlo absolutamente todo es innecesario. Basta con darse cuenta, por ejemplo, de que si Tomás no viene, de la primera condición se deduce enseguida que tiene que venir Karina. Todas las posibilidades en las que no viniera ninguno de los dos las tachamos directamente. Los algoritmos inteligentes combinan toda una serie de trucos así. Los mejores que se conocen hoy necesitan aproximadamente

$${\mathrm{1,307}}^n$$

pasos. Es un salto enorme. Para n = 100 salen, en lugar de 10³⁰, aproximadamente 4,2 · 10¹¹ pasos, lo que un ordenador hace en unos minutos.

Pero cuidado, aquí está la trampa. 1,307ⁿ sigue siendo una función exponencial. Hemos reducido la base de dos a 1,307, pero la variable n sigue en el exponente. Si n sigue creciendo, al final nos acabará aplastando igualmente. Para n = 1000, incluso 1,307ⁿ es un número de 117 cifras.

¿Y cómo sería un algoritmo que no fuera exponencial? Por ejemplo, uno que se apañara con n³ pasos. Sería polinómico y 3-SAT pertenecería entonces a la clase P. Pero entre los polinomios y las exponenciales hay todavía una zona gris: funciones que crecen más rápido que cualquier polinomio y, aun así, más despacio que cualquier exponencial. Por ejemplo,

$$2^{\sqrt{n}}.$$

Aquí en el exponente solo está la raíz cuadrada de n. Comparemos las cuatro funciones en una tabla:

Para n = 1000, $2^{\sqrt{n}}$ juega en la misma liga que n³, mientras que las dos exponenciales se han escapado a números para los que ni siquiera tenemos nombre. Las funciones como $2^{\sqrt{n}}$, que crecen más despacio que cⁿ para cualquier base c mayor que uno, se llaman subexponenciales.

Lo mismo muestra la gráfica. El eje vertical es logarítmico: cada división hacia arriba significa un número cien mil veces mayor. De lo contrario, en la imagen no cabría nada más que 2ⁿ.

En una gráfica así, las exponenciales son rectas que no dejan de subir. La roja, 2ⁿ, es más empinada que la naranja, 1,307ⁿ, pero las dos son rectas. Lo curioso es que la naranja, al principio, queda incluso por debajo de la verde, n³. No la adelanta hasta alrededor de n = 42, pero a partir de ahí ya para siempre. La azul, $2^{\sqrt{n}}$, en cambio, se va curvando y se mantiene abajo, junto a la verde.

Qué dice exactamente la ETH

Ahora ya podemos enunciar la hipótesis. La formularon en 1999 Russell Impagliazzo y Ramamohan Paturi:

Existe un número c mayor que uno tal que ningún algoritmo puede resolver 3-SAT con n letras más rápido que en aproximadamente cⁿ pasos.

¿Y en palabras sencillas? La base de la exponencial sabemos reducirla con trucos ingeniosos: de dos a 1,5, a 1,307, quizá algún día a 1,2. Pero nunca la acercaremos a uno tanto como queramos. En algún sitio hay un límite por debajo del cual no se puede bajar. Así que, según la ETH, un algoritmo de complejidad $2^{\sqrt{n}}$ no debería existir.

¿Por qué hipótesis? Porque nadie sabe demostrarla. La ETH es una suposición de trabajo, igual que en el artículo sobre P frente a NP suponemos que P ≠ NP. La mayoría de los informáticos cree en ella, porque décadas de esfuerzo solo han conseguido que la base vaya bajando poco a poco desde el dos. Pero nadie tiene una demostración.

La ETH y P frente a NP

¿Qué relación hay entre estas dos preguntas? Imagina que 3-SAT tiene una dificultad «real», el algoritmo más rápido posible. Ese algoritmo puede estar en tres franjas:

• Franja verde, polinómica. 3-SAT se puede resolver, por ejemplo, en n³ pasos. Como 3-SAT es NP-completo, se cumpliría entonces P = NP y, por supuesto, la ETH no se cumpliría.
• Franja azul, subexponencial. 3-SAT se puede resolver en $2^{\sqrt{n}}$ pasos o algo parecido. En tiempo polinómico no, así que se cumple P ≠ NP. Pero la ETH no se cumpliría.
• Franja roja, exponencial. No se puede hacer mejor que cⁿ. La ETH se cumple y, por tanto, también se cumple P ≠ NP.

En la imagen se ve que la ETH es una afirmación más fuerte que P ≠ NP. No solo dice que 3-SAT no se puede resolver en tiempo polinómico, sino que tampoco se puede en tiempo subexponencial. Quien demostrara la ETH demostraría con ello también P ≠ NP y ganaría un millón de dólares.

Y al revés: quien refutara la ETH no tendría por qué haber demostrado P = NP. Le basta con un algoritmo de la franja azul. Recuérdalo, lo usaremos dentro de un momento.

Para qué sirve la ETH

Demostrar que un problema no se puede resolver rápido es increíblemente difícil en informática. Casi no sabemos hacerlo. La ETH nos da una puerta trasera: en lugar de «el problema X es difícil», demostramos «el problema X es difícil si se cumple la ETH».

¿Cómo? Demostramos que, si el problema X se pudiera resolver rápido, también se podría resolver rápido 3-SAT. Tomemos por ejemplo este: tenemos n personas y sabemos que algunas parejas no se soportan. Queremos repartirlas en tres salas de modo que ninguna de esas parejas acabe en la misma sala. Los informáticos lo llaman coloración de un grafo con tres colores. A partir de cualquier problema 3-SAT se puede construir uno de estos de forma que el número de personas sea solo unas cuantas veces el número de letras. Así que, si se pudiera repartir a la gente en salas en tiempo subexponencial, también se podría resolver 3-SAT en tiempo subexponencial y la ETH caería.

Hoy hay cientos de resultados condicionales así. Toda una rama que estudia exactamente cuán difíciles son los distintos problemas se apoya en la ETH como una casa en sus cimientos.

La ETH tiene también una hermana más fuerte, la hipótesis fuerte del tiempo exponencial (SETH). Se centra en problemas en los que las condiciones pueden tener más de tres letras, por ejemplo diez o cien. La SETH afirma que cuanto más largas sean las condiciones que permitamos, más se acerca la mejor base posible a dos. Así que, para condiciones largas, no se podría ahorrar casi nada frente a probar a lo bruto las 2ⁿ posibilidades.

Por qué se habla ahora de la ETH

La empresa OpenAI, que conoces sobre todo por ChatGPT, publicó en octubre de 2026 un preprint, es decir, un artículo que todavía no ha pasado la revisión por pares. Se titula The Exponential Time Hypothesis is False, en español «La hipótesis del tiempo exponencial es falsa». En él afirma haber encontrado un algoritmo que resuelve 3-SAT en aproximadamente

$$2^{\frac{n}{\sqrt{\ln n}}}$$

pasos. En el exponente, por tanto, no está n sin más, sino n dividida entre la raíz cuadrada del logaritmo (natural). Ese denominador crece terriblemente despacio, pero crece, y eso basta para que la función sea subexponencial. Según el artículo, el algoritmo no solo sabe encontrar una solución, sino también contar cuántas soluciones hay.

Si fuera cierto, el algoritmo de OpenAI caería en la franja azul de la imagen de arriba. ¿Y qué significaría eso?

• La ETH caería, y con ella también la SETH y los cientos de resultados condicionales que se apoyaban en ellas. Los informáticos tendrían que tirar o reescribir un montón de «si se cumple la ETH, entonces…».
• El problema P frente a NP no quedaría resuelto. El algoritmo sigue sin ser polinómico.
• En la práctica no cambiaría casi nada. En la fórmula se esconden constantes que no conocemos. Si fueran iguales a uno, para n = 1000, $\sqrt{\ln n}$ valdría aproximadamente 2,6 y obtendríamos aproximadamente 2³⁸⁰ pasos. Eso es casi lo mismo que 1,307¹⁰⁰⁰ ≈ 2³⁸⁶ de los mejores algoritmos actuales. El nuevo algoritmo solo superaría claramente a los actuales para n todavía mayores, y por cuánto depende precisamente de esas constantes desconocidas. Así que tiene sobre todo importancia teórica. Ni el cifrado ni la banca se ven afectados.

Por ahora se trata de una afirmación sin verificar. La demostración es larga y técnica, y los expertos apenas están empezando a leerla. Muchos grandes anuncios de problemas resueltos han resultado ser erróneos en el pasado, así que, de momento, toca esperar a ver qué dicen los expertos. Escribimos este párrafo el 27 de octubre de 2026.

Solución del problema de la fiesta

Tienes que invitar a Tomás, Javier y Diego, pero no a Karina. En la imagen están las 16 posibilidades. Cada columna es una posibilidad: el círculo relleno significa que el amigo viene y el vacío, que no viene. El número rojo bajo cada columna indica la primera condición que no se cumple. La única posibilidad en la que se cumplen todas las condiciones está enmarcada en verde.

Y esto es precisamente la fuerza bruta que la ETH considera casi insuperable: para cuatro amigos, dieciséis columnas; para cien amigos, más columnas que átomos hay en nuestro cuerpo.

Véase también

• El mayor problema de la informática: P frente a NP
• Lógica proposicional
• Función exponencial
• Crecimiento exponencial