Tag Archives:: P versus NP

[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 […]

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 […]