El mayor problema de la informática: P frente a NP

Existen siete problemas matemáticos que se consideraron tan difíciles e interesantes que el Instituto Clay de Matemáticas los declaró problemas del milenio, y quien resuelva cualquiera de ellos recibirá un premio de un millón de dólares. Uno de esos problemas atañe también a la informática y se llama problema P frente a NP. Vamos a explicar de qué trata exactamente.

Ya te lo advierto: no nos engañemos pensando que será fácil de explicar. Al fin y al cabo, es un problema del milenio. Así que ve a prepararte un buen té verde 🍵 y manos a la obra. Primero veremos cuatro problemas distintos del mundo de la informática y los algoritmos. Los analizaremos y veremos qué relación tienen con las letras P y NP.

Problema n.º 1: encontrar el número más pequeño

P frente a NP tiene que ver con los algoritmos y su complejidad. Imagina que te echo encima cien papelitos, cada uno con un número escrito, y te pido que encuentres el papel en el que está escrito el número más pequeño. ¿Cuánto tiempo te llevará?

¿Medio minuto? ¿Dos minutos?

Esas unidades de tiempo no nos interesan demasiado en la informática teórica. Lo que nos interesa es más bien el número de operaciones. Podríamos preguntarlo de otra manera: ¿cuántos papelitos tengo que comprobar para estar seguro de que he encontrado el número más pequeño? La respuesta es que tengo que comprobarlos todos, porque el número más pequeño puede estar en el último papelito. Si te lanzo cien papelitos, tienes que comprobar cien papelitos. Si te lanzo mil, tienes que comprobar mil. En general, si te lanzo n papelitos, tienes que comprobar n papelitos.

A esto lo llamamos complejidad de los algoritmos. Si te lanzo n papelitos y tienes que hacer n operaciones para encontrar el número más pequeño, eso significa que este algoritmo de búsqueda del número más pequeño tiene complejidad n, a la que también llamamos complejidad lineal, porque la complejidad se describe mediante una función lineal.

Bien, has revisado los cien papelitos y has anunciado que el número más pequeño es el 17. ¿Cómo puedo comprobar que dices la verdad? No hay otra manera que volver a revisar todos los papelitos y comprobar que en ninguno hay un número menor. Es decir, tú tienes que mirar n papelitos para encontrar el número más pequeño y yo, si quiero comprobarlo, tengo que hacer lo mismo. La complejidad de verificar el resultado es, por tanto, también n, complejidad lineal.

¿Existen algoritmos en los que sea más fácil comprobar el resultado que encontrarlo?

Problema n.º 2: producto de una pareja

Imagina que echo delante de ti dos montones del mismo tamaño de papelitos, y en cada papelito hay de nuevo un número. Y ahora te pido que encuentres un número del montón A y un número del montón B cuyo producto sea 918. Por ejemplo, supongamos que tenemos estos montones de números:

$\begin{array}{rcl} A & = & {49, 11, 32, 54, 15} \\ B & = & {17, 64, 74, 61, 21} \end{array}$

¿Cómo podemos encontrar una pareja de números cuyo producto sea 918? Pues podemos sencillamente probar todas las posibilidades. ¿Cuántas hay? Bastantes: 25. Empezamos multiplicando el primer número del montón A, es decir, el 49, por cada número del montón B:

$\begin{array}{rcl} 49 \cdot 17 & = & 833 \\ 49 \cdot 64 & = & 3136 \\ 49 \cdot 74 & = & 3626 \\ 49 \cdot 61 & = & 2989 \\ 49 \cdot 21 & = & 1029 \end{array}$

Ninguna pareja de números da 918. Probamos entonces lo mismo con el resto de los números del montón A, es decir, otras cinco parejas para el 11, otras cinco para el 32, otras cinco para el 54 y las últimas cinco para el 15. En total podemos probar 25 parejas de números. Al final descubrimos que 54 · 17 = 918.

¿Cuál es la complejidad de este algoritmo? Nos interesa cuántas parejas de números hemos tenido que multiplicar. Ambos montones contenían cinco papelitos y hemos tenido que probar cada uno de los cinco números del primer montón con cada uno de los cinco números del segundo. En total hemos probado 5 · 5 = 25 combinaciones. Si te lanzara dos montones de 10 papelitos, tendrías que probar 10 · 10 = 100 combinaciones. Generalizando, si te lanzo dos montones de n papelitos, tienes que probar n · n = n² combinaciones.

Decimos que nuestro algoritmo tiene complejidad n², complejidad cuadrática, porque la describe una función cuadrática.

Pero ¿cómo de difícil será comprobar el resultado? Si me respondes que 54 y 17 son números cuyo producto es 918, ya no tengo que recorrer todas las parejas de números de ambos montones como has tenido que hacer tú. Me basta con multiplicar esta única pareja 54 · 17 para saber si tienes razón o no. Así que, mientras que para resolver este problema hay que calcular hasta n² productos, para verificar basta con calcular un solo producto. La verificación tiene, pues, complejidad constante 1.

En eso se diferencia notablemente de la tarea anterior, donde necesitábamos los mismos pasos para el cálculo y para la posterior verificación.

Esta tarea es además de un orden de magnitud más compleja que la anterior. Si te echara diez mil papelitos y te pidiera encontrar el número más pequeño, probablemente podrías encontrarlo en un día. Pero si te echara dos veces diez mil papelitos y te hiciera buscar el producto, tendrías que comprobar diez mil por diez mil productos, es decir, cien millones de cálculos. Aunque probaras un producto por segundo, tardarías unos tres años.

Problema n.º 3: suma de un subconjunto

Veamos el tercer problema. Esta vez echo delante de ti doce papelitos con números y te pido que encuentres un número cualquiera de papelitos cuya suma sea cero. Por ejemplo:

$A = {24, - 69, 1, - 15, - 76, - 60, 16, - 83, 48, - 22, 54, - 47}$

Elige de estos números un grupo cualquiera cuya suma sea 0. Por ejemplo, los números

$24 + 48 - 69 + 1$

suman 4 y por tanto no son la respuesta correcta. La respuesta correcta es el grupo de números… ¿y sabes qué? Intenta encontrarlo tú mismo como deberes 😉. Existe un único grupo de números cuya suma es 0. Al menos comprobarás lo difícil que es este problema.

Ahora necesitamos conocer la complejidad de este problema. El cálculo en sí ya no es del todo trivial y es más bien para los más curiosos. Así que, si te interesa cómo se calcula la complejidad de este problema, sigue leyendo. Si no, puedes saltar al siguiente apartado. ⏩

¿Cómo podemos encontrar un grupo de números cuya suma sea 0? Pues sencillamente tenemos que probar todas las combinaciones posibles de números. Tenemos que probar todas las parejas, todos los tríos, los grupos de cuatro, de cinco, etc., y en cada grupo tenemos que comprobar si su suma es cero. ¿Cuántas combinaciones de este tipo existen?

Veámoslo en un conjunto más pequeño de números. ¿Cuántos grupos distintos de números, es decir, subconjuntos, puedo formar con los tres números B = {5, 7, 9}? En total son ocho:

$\begin{array}{rcl} B_{1} & = & {} \\ B_{2} & = & {5} \\ B_{3} & = & {7} \\ B_{4} & = & {9} \\ B_{5} & = & {5, 9} \\ B_{6} & = & {5, 7} \\ B_{7} & = & {7, 9} \\ B_{8} & = & {5, 7, 9} \end{array}$

Fíjate en que hemos contado también el subconjunto vacío B₁. Ahora mismo no es muy útil, pero lo hemos dejado por rigor. Para simplificar el cálculo, asignaremos a cada subconjunto un vector binario. Un vector binario es simplemente una sucesión de ceros y unos, por ejemplo 00101010. Nosotros trabajaremos con vectores binarios de longitud tres. Asignamos el vector 101 al subconjunto que contiene «el primer y el tercer número del conjunto original, pero no el segundo», es decir, al conjunto {5, 9}. Asignamos el vector 110 al subconjunto que contiene «el primer y el segundo número del conjunto original, pero no el tercero», es decir, al conjunto {5, 7}, etc.

$\begin{array}{rcl} B_{1} = {} & \to & 000 \\ B_{2} = {5} & \to & 100 \\ B_{3} = {7} & \to & 010 \\ B_{4} = {9} & \to & 001 \\ B_{5} = {5, 9} & \to & 101 \\ B_{6} = {5, 7} & \to & 110 \\ B_{7} = {7, 9} & \to & 011 \\ B_{8} = {5, 7, 9} & \to & 111 \end{array}$

Vemos que cada subconjunto tiene exactamente un vector binario de longitud tres. Y cada vector binario de longitud tres corresponde exactamente a un subconjunto. Por tanto, si calculamos cuántos vectores binarios distintos de longitud n existen, obtendremos el número de combinaciones distintas que podemos formar si tenemos n números distintos de entrada. Vamos a calcularlo.

Vectores binarios de longitud uno hay dos: 0 y 1.

Los vectores binarios de longitud dos los obtenemos tomando todos los vectores binarios de longitud uno y añadiendo un 0 al final de cada uno: obtenemos los vectores 00 y 10. De nuevo tomamos todos los vectores de longitud 1 y añadimos un 1 al final: 01 y 11. Así hemos obtenido todos los vectores de longitud 2: 00, 01, 10 y 11.

Los vectores binarios de longitud tres los obtenemos tomando todos los vectores binarios de longitud dos y añadiendo al final un cero: 000, 010, 100 y 110, y un uno: 001, 011, 101 y 111.

Y así sucesivamente para cada longitud siguiente. Vemos que, cuando aumentamos en uno la longitud del vector binario, el número de vectores binarios distintos se duplica. Para longitud cuatro obtendríamos, por tanto, 2 · 2 · 2 · 2, es decir, 16 combinaciones distintas.

En general, podemos deducir que, si tenemos un conjunto M con n elementos, el número de todos los subconjuntos de M es igual al número de vectores binarios distintos de longitud n, que es

$\underset{n veces}{\underset{⏟}{2 \cdot 2 \cdot \dots \cdot 2}} = 2^{n}$

2ⁿ o n²: ¿da lo mismo? 🤷‍♂

Existen, pues, 2ⁿ subconjuntos distintos que podemos formar a partir de un conjunto de n números. En nuestro caso tenemos n = 12 números y, por tanto, tenemos que comprobar 2¹² combinaciones distintas, que son 4096 combinaciones. Decimos que este problema tiene complejidad 2ⁿ, complejidad exponencial, porque lo describe una función exponencial.

Fíjate en que el problema anterior tenía complejidad n², mientras que este tiene complejidad 2ⁿ. Se parece mucho, ¿verdad? Pero hay una gran diferencia entre tener un exponente constante y tener la variable n en el exponente. Observa que, cuando n = 4, obtenemos

$\begin{array}{rclrc} n^{2} & = & 4^{2} & = & 16 \\ 2^{n} & = & 2^{4} & = & 16 \end{array}$

Bien, de momento nos sale lo mismo. ¿Y si n = 10?

$\begin{array}{rclrc} n^{2} & = & 10^{2} & = & 100 \\ 2^{n} & = & 2^{10} & = & 1024 \end{array}$

Vaya, la función exponencial se ha disparado y de repente es unas diez veces mayor que la cuadrática. ¿Qué obtenemos para n = 20?

$\begin{array}{rclrc} n^{2} & = & 20^{2} & = & 400 \\ 2^{n} & = & 2^{20} & = & 1 048 576 \end{array}$

Para n = 20, la complejidad exponencial tiene un valor unas 2600 veces mayor que la complejidad cuadrática. Vemos, pues, que la función exponencial crece mucho más rápido que la función cuadrática. Acuérdate de esto la próxima vez que nos afecte una pandemia que se propague por la población a velocidad exponencial.

Si te lanzara, pues, veinte papelitos, tendrías que comprobar 1 048 576 combinaciones. Es bastante.

¿Cómo verificamos que el resultado es correcto?

¿Cuánto tiempo me llevará verificar que el grupo de números resultante realmente suma 0? Será bastante rápido: simplemente sumo este único grupo de números y, si su suma es igual a 0, has encontrado el grupo correcto de papelitos; si la suma es distinta, has encontrado un conjunto equivocado.

De nuevo vemos que comprobar el resultado es mucho más sencillo que encontrarlo.

Problema n.º 4: el problema del viajante

El problema del viajante es uno de los problemas algorítmicos más famosos. A grandes rasgos, tenemos un viajante de comercio que vende lluvia. Y este viajante tiene que viajar mucho para ganarse la vida. Por eso ha decidido visitar 14 de las ciudades más grandes de España. Y como no quiere derrochar, ha decidido encontrar el camino más corto posible que lo lleve por todas esas ciudades. Y nuestra tarea es encontrar ese camino más corto.

¿Cómo podemos encontrarlo? Probamos todas las posibilidades.

Podemos simplificarlo. Imaginemos que entre cada dos ciudades existe exactamente un camino más corto. ¿Cómo podemos encontrar el camino más corto que pase por todas las ciudades? Tenemos 14 ciudades. Tenemos, pues, 14 opciones para empezar. Digamos que hemos empezado en Sevilla. ¿Adónde podemos ir desde Sevilla? En teoría podemos ir a cualquier otra ciudad. Podemos elegir, por tanto, entre las 13 ciudades restantes.

Ya podemos calcular que tenemos 14 · 13 posibilidades de visitar las dos primeras ciudades: tenemos 14 opciones para empezar y luego podemos elegir entre las 13 ciudades restantes.

Cuando lleguemos a la segunda ciudad, tenemos que seguir. Ya hemos estado en dos ciudades, así que podemos viajar a una de las 12 restantes. Tenemos así 14 · 13 · 12 posibilidades de visitar las tres primeras ciudades.

Cuando hayamos visitado la tercera ciudad, tenemos que elegir una de las 11 restantes, luego una de las 10 restantes, etc.

Cuando las hayamos visitado todas, descubriremos que podíamos elegir entre un total de

$14 \cdot 13 \cdot 12 \cdot 11 \cdot 10 \cdot 9 \cdot 8 \cdot 7 \cdot 6 \cdot 5 \cdot 4 \cdot 3 \cdot 2 \cdot 1$

posibilidades. Esto te puede recordar al factorial, que se denota con un signo de exclamación. Podemos decir, pues, que este producto es igual a 14!:

$14! = 14 \cdot 13 \cdot 12 \cdot 11 \cdot 10 \cdot 9 \cdot 8 \cdot 7 \cdot 6 \cdot 5 \cdot 4 \cdot 3 \cdot 2 \cdot 1$

y, por tanto, existen 14! caminos que pasan por todas esas ciudades. ¿Es mucho? Bastante, porque

$14! = 87 178 291 200.$

En general, si buscáramos el camino más corto entre n ciudades, tendríamos que probar n! caminos distintos. La complejidad de esta solución es, por tanto, n!.

¿Cómo verificaríamos que hemos encontrado el resultado correcto? Si me dijeras que el camino más corto es de Valencia a Sevilla, luego a Zaragoza, etc., ¿cómo puedo comprobar que dices la verdad? Pues bastante difícilmente 🤷‍♂. Porque, cuando miro ese camino, no tengo manera fácil de comprobar si precisamente este camino es el más corto. En realidad tengo que hacer todo el cálculo de nuevo. La complejidad de verificar el resultado es, por tanto, también n!.

Clases P y NP

Hemos visto cuatro problemas y los algoritmos que los resuelven, y hemos analizado lo difícil que es encontrar la solución y lo difícil que es comprobarla. Podemos resumirlo en esta tabla:

Problema	Complejidad de la resolución	Complejidad de la verificación
Número más pequeño	n	n
Producto de una pareja	n²	1
Suma de un subconjunto	2ⁿ	n
Viajante	n!	n!

Ahora dividiremos nuestros problemas en dos grupos. El primer grupo estará formado por los problemas fáciles de resolver. Son los problemas que se pueden resolver con complejidad n o n² o n³ o n⁴, etc. Como las expresiones como n² se llaman polinomios, a esta clase de problemas la designamos con la letra P. Decimos, pues, que la clase P contiene los problemas que se pueden resolver en tiempo polinómico (= tienen complejidad, por ejemplo, n² o n⁷). En general, son los problemas que se pueden resolver más o menos fácilmente.

A la clase P pertenece, por tanto, el problema n.º 1, encontrar el número más pequeño, porque su complejidad de resolución es n, y también el problema n.º 2, el producto de una pareja, porque su complejidad de resolución es n²; ambas son polinomios.

La segunda clase es la clase NP. Contiene los problemas que se pueden verificar en tiempo polinómico. A la clase NP pertenecen, pues, todos los problemas excepto el último. El problema del viajante no sabemos verificarlo en tiempo polinómico. Los tres problemas anteriores sí se pueden verificar en tiempo polinómico.

El problema del viajante no sabemos ni resolverlo ni verificarlo en tiempo polinómico. Para el problema del viajante necesitaríamos, por tanto, otra clase más, que contuviera problemas todavía más difíciles. Esa clase existe, pero ahora mismo no nos interesa.

Es evidente que la clase P es un subconjunto de la clase NP. Es decir, que todo problema que está en la clase P está también en la clase NP. Tiene sentido: si somos capaces de resolver un problema en tiempo polinómico, somos capaces también de verificar el resultado en tiempo polinómico.

El problema P frente a NP

¿Y se cumple también lo contrario? ¿Está todo problema de la clase NP también en la clase P? Es decir, si existe una manera de verificar el resultado de un problema en tiempo polinómico, ¿existe también un algoritmo que resuelva ese problema en tiempo polinómico?

Por ejemplo, sabemos que somos capaces de verificar el resultado del problema n.º 3, la suma de un subconjunto, en tiempo polinómico. Pero para resolverlo hemos usado un algoritmo que no es polinómico: el algoritmo usado tiene complejidad exponencial 2ⁿ. Pero ¿sabemos con certeza que para este problema no existe ningún algoritmo con complejidad polinómica?

¡No lo sabemos!

Perfectamente podría ocurrir que para todo problema que se pueda verificar en tiempo polinómico existiera un algoritmo que resuelva ese problema en tiempo polinómico. Nosotros no lo sabemos. No sabemos demostrar la existencia de tal algoritmo, pero tampoco sabemos refutarla.

Si para todo problema de la clase NP existiera un algoritmo que lo resolviera en tiempo polinómico, significaría que la clase NP es en realidad igual a la clase P. Todos los problemas de la clase P estarían en la clase NP y todos los problemas de la clase NP estarían en la clase P: ambas clases serían iguales, coincidirían.

El problema P frente a NP es, por tanto, la pregunta de si la clase P coincide con la clase NP o si se trata de dos clases distintas de problemas.

O bien se cumple P = NP, o bien se cumple P ≠ NP. Nadie lo sabe y, si lo descubres tú, te espera un premio de un millón de dólares, fama eterna y probablemente también el Premio Turing, que es como el Nobel de los informáticos.

¿Qué pasaría si P = NP?

¿Qué pasaría si se cumpliera que P = NP? Pues no es del todo sencillo decir qué pasaría. Sabríamos que para todos los problemas de la clase NP existe un algoritmo que los resuelve en tiempo polinómico. Por ejemplo, que para nuestro problema n.º 3, la suma de un subconjunto, existe un algoritmo que lo resuelve en tiempo polinómico. Pero esto tiene tres pegas:

Saber que existe tal algoritmo no significa que seamos capaces de encontrarlo. Simplemente sabríamos que sí, que existe un algoritmo que resuelve el problema en tiempo polinómico, pero quizá no sabríamos construirlo durante otros cien años. Es algo parecido a cuando la teoría de la relatividad general predijo la existencia de los agujeros negros, pero aun así tardamos varias décadas más en conseguir la primera «fotografía» de un agujero negro.
Que exista un algoritmo que trabaje en tiempo polinómico no significa, por desgracia, que sea rápido. Podríamos encontrar un algoritmo con complejidad n¹⁰⁰. Pues también la expresión n¹⁰⁰ es un polinomio. Si comparamos las complejidades 2ⁿ y n¹⁰⁰, comprobaremos que, mientras n sea relativamente pequeño, el algoritmo con complejidad 2ⁿ todavía necesita menos operaciones. Por ejemplo, para n = 20 se cumple que 2²⁰ = 1 048 576, mientras que la expresión 20¹⁰⁰ da un número que tiene unas 130 cifras, que es un número unos 120 órdenes de magnitud mayor que 1.048.576. Nuestro algoritmo polinómico sería, por tanto, en la práctica más lento que el exponencial. Al menos mientras n sea relativamente pequeño.
Si aun así lográramos encontrar un algoritmo rápido que trabajara en tiempo polinómico, podríamos resolver muchos problemas más rápido y con mayor precisión. Eso es, por supuesto, una buena noticia, pero tiene también sus aspectos negativos. Existe un campo que se apoya en que algunos problemas son difíciles de resolver, y es la criptografía, el cifrado. Podría ocurrir que fuera mucho más fácil romper los cifrados actuales.

Inciso: como has leído hasta aquí, te desvelo como premio que la solución del problema n.º 3 es 24 + 1 − 60 + 16 − 83 + 48 + 54.

¿Qué pasaría si P ≠ NP?

Si se cumpliera que las clases de problemas P y NP son distintas, tampoco pasaría gran cosa, porque eso es más o menos el statu quo. Ahora mismo no tenemos ningún algoritmo que resuelva en tiempo polinómico algún problema difícil de NP y, si alguien demostrara que P ≠ NP, así seguiría para siempre. Mucho más sensacional sería una demostración de que P = NP.

Referencias en la cultura popular

En un episodio de Los Simpson vemos que Homer llega a una especie de realidad alternativa en la que se le revela que P = NP. Puedes verlo en youtube.com.
En Futurama, por su parte, vemos que tienen en un almacén dos carpetas, una con el nombre P y otra con el nombre NP. Puedes verlo en youtube.com.
El segundo episodio de la segunda temporada de la serie Elementary, titulado «Solve for X», trata del asesinato de un matemático que probablemente resolvió el problema P frente a NP.

« Anterior: ¿Cuánto es 1 + 2 + 5 · 0? Sobre la jerarquía de las operaciones

Siguiente: Hipótesis del tiempo exponencial (ETH) »