La Hipótesis del Tiempo Exponencial es Falsa [pdf]
Un nuevo preprint de OpenAI afirma refutar la Hipótesis del Tiempo Exponencial al dar un algoritmo de tiempo subexponencial para 3-SAT, un problema insignia NP-completo. Los comentaristas destacan que se trata de un gran avance teórico que descarta una suposición de dureza muy usada y debilita ligeramente la confianza en la creencia de que P≠NP, aunque sigue quedando muy lejos de una solución práctica o en tiempo polinómico y deja que la mayoría de los problemas de NP sigan pudiendo ser exponenciales. Gran parte de la conversación gira en torno a qué implica realmente la cota temporal concreta, por qué no hace automáticamente subexponenciales todos los problemas de NP ni rompe la criptografía, y cómo algoritmos “galácticos” como este pueden, aun así, cambiar las intuiciones sobre qué tipos de algoritmos son posibles.
Importancia y relación con P vs NP
- Muchos comentaristas ven esto como un resultado teórico enorme, “en la misma liga” que P vs NP, pero enfatizan que no resuelve P vs NP.
- Que ETH sea falsa elimina una suposición muy usada; mucho trabajo previo que dependía de ETH/SETH puede necesitar ser revisado.
- Algunos lo interpretan como una debilitación de la confianza en P≠NP; otros argumentan que en realidad no cambia mucho, salvo mostrar que nuestras intuiciones sobre problemas “difíciles” estaban equivocadas.
Qué afirma realmente el resultado
- ETH decía que k‑SAT (normalmente 3‑SAT) requiere tiempo ~2^{Ω(n)}.
- El artículo da un algoritmo subexponencial, aproximadamente 2^{n / √log n}, así que ETH es falsa.
- El hilo corrige repetidamente una confusión: esto no demuestra NP≠EXP ni NP⊊EXP.
Reducciones y por qué no se ha demostrado que NP sea subexponencial
- Matiz clave: los problemas de NP se reducen a SAT en tiempo polinómico, pero las reducciones polinómicas pueden inflar el tamaño de la instancia.
- Cotas de la forma 2^{o(n)} no se trasladan automáticamente a través de reducciones polinómicas arbitrarias; se necesitaría 2^{n^{o(1)}}.
- Por tanto, que 3‑SAT sea subexponencial no implica que todos los problemas de NP sean subexponenciales.
- Sí se transfiere a problemas reducibles linealmente a SAT (por ejemplo, ciertos problemas de conteo listados en el artículo).
Intentos de explicarlo fácil y la intuición de complejidad
- Varios comentarios ofrecen explicaciones sencillas de SAT, NP y ETH, subrayando:
- NP = verificable eficientemente (con una pista), no necesariamente resoluble eficientemente.
- Subexponencial sigue pudiendo ser astronómicamente grande; hay una enorme diferencia entre tiempo polinómico y exponencial.
Impacto práctico y algoritmos “galácticos”
- Expertos en solucionadores SAT llaman a los algoritmos “galácticos”: las constantes son tan enormes que los casos del mundo real siguen estando mejor servidos por los solucionadores existentes.
- Las instancias SAT reales suelen ser mucho más fáciles que el peor caso; no se esperan mejoras inmediatas de rendimiento.
Implicaciones más amplias y reacciones
- Algunos ven esto como un pequeño cambio de intuición hacia “quizá existan algoritmos ingeniosos que no hemos imaginado”, en línea con visiones antiguas de que muchos problemas podrían admitir algoritmos más rápidos.
- Otros se preguntan si “eficiente” en teoría de la complejidad coincide con las nociones del mundo real, sugiriendo que P vs NP podría ser un proxy mal planteado para la eficiencia práctica.
- Hay curiosidad y especulación sobre impactos en criptografía, pero el hilo señala que ningún criptosistema actual parece romperse de forma obvia por este resultado.