Tag Archives:: Complejidad computacional

[PS 13 Nov 2017] Norbert Blum ha publicado su propio análisis del error que cometió en la demostración del teorema 6 de su artículo; afirma que trabaja en su solución, pero no parece posible arreglar su demostración. Los interesados en los detalles disfrutarán con Norbert Blum, “The mistake in “A Solution of the P versus NP. Problem”,” 11 Oct […]

László Babai (Premio Knuth 2015) afirmó en diciembre de 2015 haber demostrado que la complejidad algorítmica del problema del isomorfismo de grafos es cuasipolinómica (LCMF, 11 Dic 2015). El matemático peruano Harald A. Helfgott ha verificado la demostración en detalle y afirma que es correcta. El 14 de enero impartió una charla Bourbaki en el Instituto Henri Poincaré de […]

El famoso László Babai (Premio Knuth 2015) afirma haber demostrado que la complejidad algorítmica del problema del isomorfismo de grafos es cuasipolinómica. Catedrático de la Universidad de Chicago, EEUU, ha impartido una charla en su propia universidad para explicar su demostración, basada en combinar la teoría de grupos y la combinatoria. El vídeo de la charla permite hacerse una […]

Saber si un algoritmo se detiene tras un número finito de pasos, el problema de la parada, es un problema indecidible. Alan Turing demostró en 1936 que no hay ningún algoritmo universal capaz de decidir si cualquier otro algoritmo parará o no aplicado a una entrada arbitraria. La idea de la demostración es similar a decidir si la frase […]

El famoso físico teórico de 74 años de edad Leonard Susskind (Univ. Stanford, California) ha puesto de moda una camiseta con el logotipo “I ♥ Complexity.” ¿Qué busca en la complejidad computacional un físico teórico experto en gravedad cuántica? Mucho más que una solución a la llamada paradoja del “muro de fuego” (firewall) en agujeros negros. Una nueva visión […]