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?

A primera vista, uno podría pensar que la respuesta es "no mucho". "Demostrar que P no es igual a NP acabaría de confirmar lo que ya casi todo el mundo asume como la verdad, a efectos prácticos", explica Scott Aaronson, investigador de complejidad en el Laboratorio de Inteligencia Artificial y Ciencias Informáticas del MIT.

Por ejemplo, nuestra incapacidad para trabajar de forma eficiente con enormes números compuestos (un clásico problema NP) constituye la base de la criptografía moderna—que subyace en múltiples áreas, desde la seguridad nacional a las compras en Amazon.com. "No necesitamos una prueba formal de que P no es igual a NP para depender de la conjetura", señala Aaronson. "Los programadores conocen el problema y les interesaría muchísimo ver que se prueba que P no es igual a NP, pero a nivel del día a día, saben que la reformulación de un problema NP en algo más sencillo tiene mucho más sentido que tratar de resolver el problema matemático del siglo".

Dado que los problemas de clase NP son tan penetrantes (incluso los rompecabezas sudoku y las búsquedas de horarios de aerolíneas en Bing.com son computacionalmente "difíciles"), constantemente se están descubriendo soluciones innovadoras. La optimización estocástica, por ejemplo, imita la aleatoriedad encontrada en los sistemas físicos (como la refrigeración de metales o la mutación del ADN) con el fin de producir soluciones "suficientemente buenas" en vez de otras que sean difíciles a nivel computacional.

Los intentos por "hacer frente" a la suposición de que P no es igual a NP "nos ayudan a desarrollar nuevas tecnologías mentales", afirma Richard Lipton, científico informático del Georgia Tech encargado del estudio del problema P versus NP. "Aunque llevamos escribiendo algoritmos durante décadas, no entendemos completamente lo que son capaces de hacer," añade. "Así que, incluso si demostrásemos que P no es igual a NP—algo que ya creemos todos—tendríamos que ampliar de manera sustancial nuestra comprensión de esas capacidades, y hacer que muchas cosas nuevas fueran posibles usando los ordenadores, además de todas las soluciones inteligentes que ya hemos encontrado".

Por tanto, si el progreso incremental puede aún generar innovación útil, ¿por qué los titanes de la investigación industrial como Google, Microsoft y HP (los cuales se negaron a hacer comentarios para este artículo) no dedican sus inmensos equipos de investigadores a resolver el puzzle sobre P y NP? "Probar algo negativo es increíblemente difícil y, a partir del punto de vista de una gran empresa, probablemente no tenga mucho impacto en el próximo trimestre financiero, o incluso en los próximos años de su negocio," afirma Lipton. "Es más una cuestión a largo plazo".

Por supuesto, siempre existe la alternativa: demostrar que P de hecho es igual a NP. Pero no debemos emocionarnos con ese tema, señala Aaronson. "Hay buenas razones por las que muy pocas personas creen que P es igual a NP," asegura. "Si así fuera, estaríamos viviendo en un universo muy distinto y probablemente ya nos habríamos dado cuenta".