Es posible que hayas oído hablar del famoso problema P versus NP. Si puedes probar o refutar su ecuación crípticamente corta, serías un millón de dólares más rico, y tal vez incluso miles de millones de dólares, dependiendo de tus escrúpulos.
La importancia de P versus NP está principalmente en sus consecuencias para la computación. Sucede que es uno de los siete problemas del Premio Millennium, lo que significa que el Clay Mathematics Institute de Cambridge, Massachusetts otorgará 1 millón de dólares a quienquiera que logre probar o refutar la declaración. Pero si pruebas que P, de hecho, es igual a NP, ni siquiera necesitarías el premio de 1 millón de dólares. Como explicó el científico teórico Scott Aaronson la semana pasada en una conferencia en un auditorio en el Laboratorio Nacional de Los Álamos en Nuevo México, demostrando que P = NP abrirías algunas posibilidades intrigantes.
“Si alguien prueba que P = NP, lo primero que deben hacer es robar 200 mil millones de dólares en bitcoins. La segunda cosa que deberían hacer es resolver el resto de problemas del Premio del Milenio”, dijo Aaronson.
Para comprender esto, debes saber que las computadoras son dispositivos que resuelven problemas, resumidos en un código legible por el dispositivo de computación física, basado en los principios expuestos por Alan Turing. Resolver problemas lleva varios pasos y una cierta cantidad de tiempo, y la cantidad de tiempo requerido aumenta a medida que el problema aumenta.
“P” se refiere a los problemas que las computadoras resuelven todo el tiempo, desde algo tan simple como multiplicar dos números hasta tareas más complejas como navegar por Internet. A medida que un problema crece en complejidad, la cantidad de tiempo que lleva resolverlo crece en “tiempo polinomial”, donde un polinomio es un número con una potencia y un coeficiente (como n2). Si un problema es solucionable en n2 veces y duplica el tamaño de la entrada, entonces la cantidad de tiempo que tomaría resolverlo aumentaría en cuatro.
Sin embargo, hay muchos problemas en los que se puede determinar que una respuesta dada es correcta en el tiempo polinomial, pero llegar a esa respuesta puede o no ser posible en el tiempo polinómico. Estos se denominan “tiempo polinomial no determinista” o problemas de NP. El sudoku es un problema de NP: difícil de resolver, fácil de verificar. Otro ejemplo importante hoy en día es factorizar grandes números en números primos. Por ahora, al menos, se necesita mucho tiempo, más lento que el tiempo polinomial, para factorizar números muy grandes en números primos, pero verificar que una respuesta sea correcta es tan simple como multiplicar los números resultantes. De hecho, esta idea exacta es la base del cifrado moderno, que se basa en la generación de claves de seguridad que son fáciles de verificar pero difíciles de descifrar.
Las pruebas matemáticas más recientes han encontrado, y podrían seguir encontrando, soluciones P para algunos de estos problemas de NP. El problema de P vs NP pregunta si cada problema de NP tiene una solución de P, o si existe algún problema de NP que no pueda resolverse en P. Parece que debería ser obvio que P no es igual a NP, pero no está rigurosamente y matemáticamente probado. Y si prueba que P es igual a NP, también habrá demostrado que hay algoritmos de tiempo polinomial para una gran cantidad de problemas informáticos muy importantes. Podrías hacerte muy rico: las claves de minería y seguridad de bitcoin se basan en problemas de NP difíciles de resolver y fáciles de verificar.
Las computadoras cuánticas, que se basan en diferentes matemáticas que las computadoras clásicas, no prometen soluciones P para cada problema de NP. Una vez se pensó que podrían resolver la clase más difícil de problemas de NP, llamados problemas de NP completa. Si pudieras encontrar una solución eficiente para esos, podrías encontrar soluciones eficientes para todos los problemas de NP. Esto incluye el problema del vendedor ambulante y una serie de otros problemas de optimización similares. Pero las computadoras cuánticas no han estado a la altura de esta exageración. En cambio, las computadoras cuánticas podrían resolver algunos problemas de P en un tiempo más corto (como con un polinomio más bajo) o mover algunos problemas de NP a la generalización cuántica de P, llamada BQP o “Tiempo polinomial cuántico de error limitado”.
Así que ve y trata de probar una y otra vez que P hace o no igual a NP. Si tienes éxito, ganarás al menos un millón de dólares, y tal vez mucho, mucho más. Si no tienes éxito, bueno, con suerte habrás liderado una teoría computacional de investigación de vida significativa.
Fuente: es.gizmodo.com