P contra NP el problema del milenio, explicado de forma sencilla

Existen 10 problemas matemáticos especialmente importantes dotados con un premio de un millón de dólares: los problemas del mileno. Hoy vamos a explicar uno de los más famosos

El problema que nos ocupa hoy será el de P contra NP, quizás uno de los títulos más sonoros y conocidos de todos los problemas del milenio, pero también uno de los más crípticos. De este problema ya os hablamos un poco hace una semana cuando comentamos los descubrimientos que habían hecho un grupo de investigadores sobre el videojuego Super Mario Bros. y cómo este se relacionaba con los problemas sobre la complejidad matemática.

La verdad es que el post recibió bastante atención por lo que hemos decidido hacer una segunda parte explicando más en detalle (pero de forma sencilla, esperamos) qué significa P contra NP y por qué es importante incluso para nuestro día a día.

Por cierto, como dato extra hace poco se descubrió que el juego TrackMania, de Ubisoft, puede considerarse NP completo, es decir, resolverlo con un algoritmo en tiempo polinomial significa ganar 1 millón de dólares y fama matemática sin precedentes. Ahora igual suena un poco confuso, pero al final del post seguro que entendéis de lo que hablamos.

¿Quién ese tal “P” del que hablan los matemáticos?

“P” es el conjunto de todos los problemas matemáticos que se pueden resolver en tiempo polinomial. Dicho en castellano lleva algo más de tiempo, pero no es complicado. El principal obstáculo a la hora de resolver un problema matemático es que cuantos más elementos tenemos, más tardamos en conseguir la solución.

Por ejemplo, si nos piden buscar el número más grande de entre 5 números, tardamos mucho menos que si nos dan 1000. Por eso el tiempo que tarda en resolverse un problema matemático se suele medir en función del número de elementos que tiene el problema.

Polynomial

En este sencillo ejemplo de buscar el número mayor, el tiempo que tardamos en resolverlo aumenta igual que la cantidad de números que nos dan. Otros problemas matemáticos puede tener otro tipo de relaciones en lo que la complejidad (el tiempo) aumenta como el número de elementos al cuadrado, por ejemplo.

Todos los problemas que tienen una relación polinomial entre el tiempo que se tardan en resolver (o el número de pasos a dar, o su complejidad) y el número de elementos entran en la categoría de “problemas resolubles en tiempo polinomial” o de forma resumida: “P” que hace referencia a Polinomial.

Qué significa NP

matematicas

Sin embargo no todos los problemas entran dentro de esta categoría. Por ejemplo, encontrar los números primos de un número dado es mucho más complejo que buscar en máximo en una lista. De hecho el tiempo que se requiere para resolver este tipo de problemas no guarda una relación polinomial con la magnitud del número.

Este tipo de problemas matemáticos generalmente tienen una relación exponencial, es decir, el tiempo necesario es un número elevado a la cantidad de elementos que tenemos. Este tipo de problemas, entran dentro del grupo “NP” (Polinomios No-deterministas) que engloba también todos los problemas de tipo “P”.

Por qué se pelean P y NP

pversusNP

La pelea “P contra NP” no es una pelea real sino que es una forma que tienen los matemáticos de abreviar la pregunta que se formula en el problema del mileno: ¿Es NP equivalente a P? Es decir, ¿existe alguna forma de resolver los problemas NP con un algoritmo de tiempo polinomial?

Otra forma de entender esta pregunta es ir a un punto de vista más profundo, en el que lo que se quiere resolver es si P y NP son dos conjuntos diferentes o simplemente parecen diferentes porque no somos lo suficientemente inteligentes para resolver un problema NP en tiempo polinomial.

Por qué nos interesa a todos que P no sea NP

tarjeta-credito

Para entender la importancia de este problema del milenio, vamos con un ejemplo. Como hemos dicho antes, encontrar los factores primos que componen un número o buscar números primos es un problema NP, lo que significa que necesitamos mucho tiempo y potencia de computación cuando trabajamos con números muy grandes.

Es por esto, entre otras cosas, que los números primos valen tanto dinero y son utilizados en los sistemas de cifrado y seguridad de los bancos, ejércitos… incluso aplicaciones de mensajería seguras. La segunda parte de este ejemplo es relativo a P, ya que comprobar que unos números dados son factores primos de otro mayor es un problema de tipo P y por tanto computacionalmente más accesible.

Los sistemas de cifrado entonces se basan en la idea de que encontrar la solución es muy costoso, pero si sabes la solución, comprobar que una solución es válida es muy fácil. Es decir, para crear un sistema de cifrado necesitas resolver un problema NP, pero para usarlo tan solo tienes que trabajar con un problema P.

Ahora bien, si resultara que P y NP son en realidad el mismo tipo de problemas y alguien consigue encontrar una forma de resolver problemas NP en tiempo polinomial, eso significa que, por ejemplo, crackear un sistema de seguridad basado en números primos es igual de sencillo que utilizar este sistema de seguridad. Por lo tanto, automáticamente tendríamos que cambiar todos los sistemas de seguridad online del mundo.

Buscando la solución a un problema del milenio del que ya sabemos la respuesta

Solution

Una de las cosas más curiosas de los problemas del milenio, y en particular de nuestro P contra NP, es que la mayor parte de la comunidad matemática está de acuerdo en cuál es la solución y la respuesta al problema, pero esta sólo se puede dar por válida si tiene detrás una demostración matemática rigurosa que la soporte.

En este caso, por ejemplo, la inmensa mayoría de los matemáticos (todos menos algún friki que vive en otro mundo) están de acuerdo en que P y NP son problemas diferentes y que no se puede resolver un problema NP en tiempo polinomial. Pero la falta de un prueba matemática rigurosa siempre deja la puerta abierta a que pueda ser de otra manera.

En cualquier caso, si alguno se aburre mucho puede intentar resolver este problema del milenio y llevarse un millón de dólares. Aunque curiosamente, no está muy bien visto entre los matemáticos aceptar el dinero; pero bueno, ya sabemos que para ser matemático hay que pasar antes un examen de “ser raro”, que en España llamamos: Grado en Matemáticas.