Se produjo un gran interés entre los programadores y científicos informáticos la semana pasada debido al último intento por resolver una de las preguntas más desconcertantes de la informática: el llamado problema «P versus NP». Vinay Deolalikar, científico de investigación en los laboratorios de HP en Palo Alto, California, publicó su «prueba» por internet y la envió a varios expertos en el campo el 6 de agosto. Sus colegas inmediatamente comenzaron a diseccionar la prueba en blogs y wikis académicas.
Las reacciones iniciales fueron respetuosas pero escépticas, y el consenso actual es que el enfoque de Deolalikar es, fundamentalmente, defectuoso.
Una prueba sólida haría que Deolalikar ganase fama y fortuna. El Instituto Clay de Matemáticas en Cambridge, Massachusetts, ha clasificado a «P versus NP» como uno de sus problemas «del Milenio», y ofrece 1 millón de dólares a cualquier persona que proporcione una prueba verificada.
Sin embargo, «P versus NP» es algo más que un rompecabezas matemático abstracto. Su objetivo es determinar—de una vez por todas—qué tipo de problemas se pueden resolver con ordenadores, y cuáles no. Los problemas de clase «P» son «fáciles» de resolver para los ordenadores; es decir, las soluciones a estos problemas pueden ser calculadas en una cantidad razonable de tiempo, en comparación con la complejidad del problema. Por otro lado, con los problemas de tipo «NP», la solución podría ser muy difícil de encontrar—quizá requeriría miles de millones de años de computación—pero una vez encontrada, es fácil de comprobar. (Imaginemos un rompecabezas: encontrar el orden correcto de las piezas es difícil, pero podemos saber que el puzzle se ha terminado correctamente con sólo mirarlo.)
Los problemas de clase NP incluyen muchos problemas de patrones y optimización, que son de gran interés práctico, como por ejemplo la capacidad de determinar la colocación óptima de los transistores en un chip de silicio, el desarrollo de modelos precisos de previsión financiera, o el análisis del comportamiento del pliegue de proteínas en una célula.
El «problema P versus NP» plantea si estas dos clases son en realidad idénticas, es decir, si todos los problemas NP son también un problema P. Si P es igual a NP, todos los problemas NP contendrían un atajo oculto, lo que permitiría que los ordenadores encontrasen rápidamente soluciones perfectas. Pero si P no es igual a NP, entonces no existen dichos atajos, y la potencia de resolución de problemas de los ordenadores seguirá siendo fundamental y permanentemente limitada. La experiencia práctica sugiere abrumadoramente que P no es igual a NP. Sin embargo, hasta que alguien ofrezca una prueba matemática sólida, la validez de la hipótesis queda abierta.
Incluso si la prueba de Deolalikar resultara ser sólida, la cuestión seguiría existiendo—¿qué impacto tendría esta prueba en las áreas relevantes de la informática?
Más información en MIT
