Tag Archives:: P versus NP

[PS 31 Ago 2017] Norbert Blum se ha retractado de su demostración (arXiv 30 Aug 2017). “The proof is wrong. I shall elaborate precisely what the mistake is. For doing this, I need some time.” Cuando el propio Blum sepa dónde está su error ha prometido comunicarlo en su página web. [/PS]. [PS 19 Ago 2017] Ya se conoce […]

La solución al problema NP=P debe ser obtenida en el paradigma de la computación con máquinas de Turing. Sin embargo, hay otros paradigmas de computación que no son Turing, como la memcomputación (un tipo de computación analógica neuronal basada en memristores y otros memdispositivos). Un nuevo artículo presenta un memcomputador que implementa un algoritmo NP completo y demuestra que […]

Las clases de complejidad clásicas y cuánticas se relacionan entre sí de una forma complicada que todavía no conocemos en detalle y por ahora todo son hipótesis. Las clases P y BQP son las clases de problemas resolubles de forma eficiente (polinómica) en ordenadores clásicos y cuánticos, resp. Las clases NP y QMA contienen los problemas de decisión que […]

El estado actual del problema P versus NP se resume en que el problema sigue abierto. Aunque se han hecho grandes avances, no se atisba que una demostración vaya a ser obtenida en las próximas décadas. ¿Pueden los computadores cuánticos resolver los problemas NP completos en tiempo polinomial? Nadie lo sabe, pero la respuesta oficial es que parece que […]