El problema "P «vs» NP"

Muchas conexiones entre sistemas usan accesos a través de Clave Pública. Para acceder a tu espacio personal en cualquier web, lo haces a través de tu usuario y contraseña que es almacenada cifrada. Para acceder a tu cuenta bancaria, usas un código que también se almacena cifrado. Los bancos protegen toda la información cifrándola. Las criptomonedas basan todo su funcionamiento en claves criptográficas. Los servicios de inteligencia de todos los países usan la criptografía para mantener seguras sus comunicaciones… Pero... ¿sabías que si alguien resuelve un problema matemático tendrá acceso a todo lo anterior? Se trata del problema conocido como "P «vs» NP". Para entender el problema necesitamos saber qué es la teoría de la complejidad. Ésta estudia cómo crece el coste en tiempo/memoria en función del tamaño de este problema. Por ejemplo, queremos ordenar varios números de mayor a menor, y para ello tenemos diferentes algoritmos. El primer algoritmo nos da el siguiente resultado:

Cantidad de números a ordenar	10	100	1000	10000
Tiempo (s)	1	2	3	4

En el caso anterior tenemos una complejidad lineal, ya que el crecimiento es constante. Pero se pueden dar casos peores:

Cantidad de números a ordenar	10	100	1000	10000	10000
Tiempo (s)	1	2	4	8	16

Este ejemplo se trata de una complejidad exponencial (¡e incluso las hay peores!). Entonces, decimos que un problema tiene la complejidad del mejor algoritmo que lo resuelve. Para esto sirve la teoría de la complejidad. Gracias a ella identificamos que hay problemas cuya complejidad crece de forma tan rápida que no merece la pena destinar recursos a su resolución. Y es en esto en los que se basa la criptografía moderna. En concreto, se basa en la complejidad que conlleva el problema de descomponer factorialmente cifras con muchos números decimales. Actualmente, el algoritmo más eficiente que descompuso un número de 200 cifras decimales en menor tiempo lo hizo en ¡18 meses! (¿Te suena que algunos bancos piden actualizar tu contraseña cada 12 meses?).

Volviendo a P vs NP

Pero ahora volvamos al título del problema. En teoría de la complejidad se llama:

NP al conjunto de problemas en los que se puede comprobar en un tiempo polinomial, es decir, en un tiempo razonable, si una solución es correcta o no.
P al conjunto de problemas para los cuales se puede encontrar en un tiempo polinomial, es decir, en un tiempo razonable una solución.

Con esta descripción, vemos que el problema de descomponer una cifra con un gran número de decimales se trata de un problema NP. Sabiendo esto, vemos que si un problema forma parte del grupo P, también está en NP, pero la pregunta es… ¿también pasa al revés? Intuitivamente, parece obvio que no, pero aquí viene la sorpresa: esto no está demostrado matemáticamente y no se puede ni afirmar ni desmentir categóricamente. P vs NP es uno de los problemas llamados “Problemas del milenio”, premiado por el Instituto Clay de Matemáticas con un millón de euros a la persona que pueda confirmar (o desmentir) que P = NP. En el caso de confirmarse obligaría a replantear toda la criptografía moderna. A día de hoy, no podemos saber si los problemas NP son inasumibles o, simplemente, no hemos encontrado el algoritmo que los resuelve en un tiempo razonable. Por lo tanto, al no haber evidencia científica que diga que los problemas NP no pueden resolverse en un tiempo razonable, seguir utilizando los métodos actuales de criptografía asumiendo que son seguros, es una cuestión de fé.