¿P=NP?: Si resuelves este problema matemático, podrías “robar” todos los bitcoins del mundo

El Clay Mathematics Institute de Cambridge ha incluido al problema P versus NP como uno de los siete problemas del Premio Millennium y ha anunciado que, si alguien lo resuelve, ganaría un millón de dólares.

Sin embargo, la resolución de este ejercicio matemático resolvería una de las cuestiones más importantes de la historia. De acuerdo con el científico teórico Scott Aaronson, el millón de dólares no sería necesario:

“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”.

¿Qué encierra P y NP?

Las computadoras parecieran resolver cualquier tipo de problemas matemáticos con facilidad, pero ocultan mucho detrás del resultado.

Las máquinas trabajan bajo la computación física basada en los principios expuestos por Alan Turing. La letra P se refiere a aquellos cálculos que se realizan a través de un tiempo polinomial, donde un polinomio es un número con una potencia y un coeficiente. Operaciones como la multiplicación de dos números o la navegación de internet se rigen bajo este modelo.

Sin embargo, existen problemas matemáticos que no son aplicables bajo el tiempo polinómico: son difíciles de calcular, pero fáciles de verificar. El ejemplo más común: dado un mapa, encontrar el camino más corto para visitar n ciudades de una sola vez y volver al punto de origen. U otro: los sudokus. No hay fórmula exacta para ver que número lleva cada celda, pero una vez que lo encuentras, puedes verificar rápidamente por qué va ahí.

Estos problemas son los llamados NP, quienes existen en un limbo informático en el que ni son considerados como ejercicios sin solución (indecidibles) ni son irresolubles (intratables). Son la base del cifrado, el cual sirve para la generación de claves de seguridad en el mundo.   

La computadora con el algortimo más eficiente en el tratamiento de NP tardó 18 meses en descomponer en factores un número de 200 cifras decimales, sobre el cual está escrito la criptografía moderna.

"Aunque llevamos escribiendo algoritmos durante décadas, no entendemos completamente lo que son capaces de hacer," mencionó Richard Lipton, científico informático del Georgia Tech a MIT. "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". Pese a ello, siempre estará la opción de comprobar que P es igual a NP.

La pregunta está en el aire: ¿Todos los problemas P tienen solución en base NP y viceversa? Si lo resuelves, además de un millón de dólares, solo tu malicia podría determinar tus límites.