El ingeniero y matemático Vinay Deolalikar ha anunciado que ha demostrado que P ≠ NP.
La teoría de complejidad computacional es parte de la teoría de la computación que analiza los recursos utilizados durante el cálculo asociado a la resolución de un problema. Los recursos más estudiados suelen ser el tiempo de ejecución del algoritmo y el espacio -memoria- utilizado por el ordenador durante el proceso.
Un problema de decisión -cuestión en algún sistema formal con una respuesta sí o no- es:
- de tipo P si puede resolverse en una máquina de Turing determinista -por ejemplo, un ordenador- en tiempo polinómico; de otro modo, la relación entre el tamaño del problema y el tiempo de ejecución es polinómica;
- de tipo NP si puede resolverse en una máquina de Turing no determinista en tiempo polinómico, es decir, al contrario que las de tipo P, no puede resolverse en un ordenador en un tiempo razonable (con los algoritmos conocidos).
La pregunta ¿P = NP? es uno de los famosos Problemas del Milenio premiados con un millón de dólares por el Clay Mathematics Institute.
Parece que la demostración dada por Vinay Deolalikar -más de 100 páginas de física estadística y varias áreas de las matemáticas- tiene buen aspecto para los especialistas en la materia, aunque quedan aún muchas comprobaciones por realizar…
Más información:
- Vinay Deolalikar, P ≠ NP [6 de agosto de 2010]
- The P-versus-NP-page
- Greg Baker, P ≠ NP [7 de agosto de 2010]
- Una copa de cava y la demostración de P ≠ NP de Vinay Deolalikar, Francis (th) E mule Science’s News [9 de agosto de 2010]
- Pues igual resulta que P ≠ NP…, Gaussianos [9 de agosto de 2010]
Reblogueó esto en Martams's Blogy comentado:
#HaceSeisAños ¿Una prueba de que P≠NP?
Me gustaMe gusta