Lunes, 16 de noviembre de 2026
Portada de las 21:50
Todos los periódicos y la radio, en unoEscrito por IA a partir de Hacker News · Cómo se hace
Hacker News
Ciencia · argmin.net

Algoritmos eficientes, la hipótesis del tiempo exponencial y perder el hilo

Ben Recht, en su blog argmin, repasa cómo la teoría de la complejidad nunca definió bien qué es un algoritmo eficiente y lo aplica al supuesto algoritmo subexponencial para SAT de OpenAI, que según él solo mejora más allá de un umbral inimaginable. Los comentarios le discuten el enfoque.

Foto: vía argmin.net

Leer el artículo aquíArtículo original (argmin.net) 57 comentarios en Hacker News

Escucha la noticia3 min

El texto arranca en 1965, cuando Jack Edmonds ideó un algoritmo para hallar un emparejamiento máximo en un grafo y quiso argumentar que era «bueno». Enumerar todas las soluciones daba un resultado correcto pero «no bueno», por exponencial. Edmonds dedicó dos páginas a definir «bueno»: un tiempo acotado por una función del tamaño del problema, válido para cualquier tamaño. Reconoció que el criterio era imperfecto y citó el método símplex como ejemplo de algoritmo útil que quizá no lo cumpliera. Su algoritmo tenía una cota de n^4.

Según el autor, Edmonds no justificó más por qué el tiempo exponencial es malo, y formalistas posteriores como Richard Karp adoptaron «tiempo polinómico» como sinónimo de bueno. Para el autor es una definición imperfecta: un algoritmo que escala como n^1000 es polinómico pero nada bueno, y de ahí salen los «algoritmos galácticos», cuyos tiempos de ejecución los hacen irrealizables en la práctica. El resultado, dice, es un zoo de resultados de complejidad desligados de la realidad del cómputo.

Después pasa a lo que OpenAI anunció esta semana: un algoritmo para el problema de satisfacibilidad (SAT) en «tiempo subexponencial», presentado en Twitter como el mayor hito de la teoría de la computación en 50 años. Al preguntar a ChatGPT por el artículo, el autor descubre que el algoritmo ejecuta búsqueda exhaustiva, la misma que Edmonds calificó de mala, mientras el número de variables sea inferior a 10^(10^22), aproximadamente. Compara esa cifra con los unos 10^80 átomos del universo. Para cualquier problema imaginable el procedimiento sigue siendo exponencial, y la mejora solo aparece en un «vecindario de infinito» incognoscible. Dice haberlo confirmado con Claude.

En las notas, el autor recuerda que el símplex es técnicamente exponencial en el peor caso y aun así es de los algoritmos más usados del mundo. También señala que los solucionadores SAT convencionales resuelven problemas industriales con millones de variables, y que alguien en Intel resolvió uno con mil millones de variables y 4.000 millones de cláusulas en un día. Su predicción es que P=NP acabará siendo cierto «en sentido galáctico» y que solo habremos aprendido que llevamos cincuenta años respondiendo a la pregunta equivocada.

En Hacker News

«Efficient algorithms, the Exponential Time Hypothesis, and losing the plot» · puesto 16 · 91 puntos · enviado por sebg

Lo que dicen los comentarios

La mayoría de los comentarios discrepa del enfoque del autor. Varios sostienen que malinterpreta la teoría de la complejidad: la distinción entre exponencial y polinómico tiene un fundamento sólido (los polinomios son cerrados bajo composición) y un P=NP galáctico seguiría siendo un resultado matemático enorme. Otros recuerdan que umbrales así son habituales en algoritmos galácticos y no afectan a la notación O grande, y que el resultado de OpenAI, aunque interesante, no es tan profundo ni tan novedoso: ya se conocían problemas NP-completos con algoritmos subexponenciales. También se apunta que la ETH se formula hoy mejor como la «Satisfiability Hypothesis». Hay quien pide una alternativa concreta al análisis de complejidad temporal, y quien reconoce que el hallazgo del umbral es chocante si el artículo no lo destaca.

  • El autor parece malinterpretar la teoría de la complejidad. Lo de exponencial = malo y polinómico = bueno pudo ser casi arbitrario al principio, pero desde entonces ha encontrado un fundamento mucho más sólido.
    — simiones, leer el comentario
  • He visto muchas críticas a la practicidad del análisis de complejidad temporal, pero nunca un artículo que diga por qué hay que sustituirlo. Sin sustituto, volvemos a analizar problemas sin ningún marco, lo cual parece peor.
    — inkysigma, leer el comentario
  • Mucha gente dice ya que la ETH se formuló de forma demasiado fuerte y que la hipótesis correcta es la SH, la Satisfiability Hypothesis, que admite mejoras no polinómicas en el exponente, justo lo que demostró ChatGPT.
    — emil-lp, leer el comentario
  • Para la complejidad O grande es irrelevante lo que pase por debajo de un umbral constante, así que el algoritmo usa el enfoque más simple. Descartarlo por dejar una optimización obvia sin hacer es raro: solo puede mejorar.
    — yorwba, leer el comentario
  • No creo que importe: es lo normal en los algoritmos galácticos. Se podría apuntar ese cañón contra más del 95 % de la investigación matemática. La complejidad es interesante y divertida, ¿no basta con eso?
    — npinsker, leer el comentario

Pregunta sobre esta noticia

Respuestas automáticas a partir de las noticias de El Autómata, sus fuentes y la radio. Pueden contener errores: comprueba los enlaces.

Fuentes

Esta noticia la ha redactado una inteligencia artificial a partir de las fuentes citadas, con el criterio editorial de El Autómata (equilibrio, atribución y solo hechos publicados). Puede contener errores: consulta las fuentes originales. Modelo: claude-sonnet-5.5.