martes, 10 de agosto de 2010

Demostración de que P != NP

Acabo de leer en Barrapunto que un investigador de HP tiene una prueba (aún no contrastada) de que las clases de complejidad P y NP son distintas. Podéis acceder al paper con la demostración aquí.
Me ha traído a la mente viejos recuerdos de la facultad, en las clases de análisis de algoritmos cuando estudiábamos problemas P-Completos y NP-Completos, y un profesor nos comentó que uno de los grandes misterios por resolver era si en realidad la P-Completitud era distinta de la NP-Completitud.
De confirmarse la demostración, se trataría de un hito muy importante en la historia de las matemáticas.

Actualización: Si la demostración se confirma, el tipo podría recibir un premio de un millón de dólares, al igual que hace poco no lo hizo Grigory Perelman al resolver la Conjetura de Poincaré.

2 comentarios:

MarcG dijo...

Argh!, complejidad P y NP... y los problemas NP-Completos...

Informática teórica...

¡Qué recuerdos de la Facultad!

Saludos.

Manuel Pereira dijo...

Leo en ALT1040 que matemáticos de todo el mundo están analizando la demostración, y parece no ser válida (aunque el camino seguido sí que podría serlo...).
Más información aquí: http://alt1040.com/2010/08/p-versus-np-y-la-matematica-20