3.17. P versus NP


P versus NP es uno de los siete “problemas del milenio”, §26, y la recompensa por resolverlo es de 1 millón de dólares. Es, posiblemente, el más fácil de entender de los siete... así que merece la pena intentarlo. Tiene que ver con la complejidad para resolver distintos tipos de problemas. Hay problemas que con unas pocas cuentas salen rápido (los llamados problemas tipo P), mientras que hay otros que parece que requieren muchas más cuentas (los llamados problemas tipo NP). Pero, claro, todo esto habrá que explicarlo un poco mejor...

Empecemos con un ejemplo sencillo. Imaginad que tenemos 5 cartas numeradas del 1 al 5. En principio están barajadas y lo que queremos es ordenarlas en sentido ascendente, es decir: 1, 2, 3, 4 y 5. Hay dos algoritmos o métodos que a uno se le ocurren, así, a primera vista para conseguirlo:

Método 1: Vamos pasando las cartas del mazo hasta que aparece el número 1. Entonces la sacamos del montón y la ponemos boca abajo aparte. Ahora buscamos la carta número 2 en el montón de cuatro cartas que queda: la sacamos y la ponemos aparte detrás de la 1. Nos quedan ya tres cartas solo. Buscamos la número 3 y la sacamos del montón. Y luego lo mismo para la 4 y la 5.

¿Cúanto tiempo nos llevaría esto? No mucho, ¿verdad? Por hacer un poco de cuentas, vamos a suponer que cada vez que miremos una carta del montón eso nos lleve un segundo. Cuando buscamos la carta número 1 en el mazo, nos puede aparecer justo la primera (1 segundo de tiempo), pero también podemos tener mala suerte y que se encuentre la última, o sea, que tendríamos que descubrir y mirar las 5 cartas: 5 segundos. Pues vamos a ser pesimistas y ponernos siempre en el peor de los casos, y que la carta que buscamos aparezca la última. Ya tenemos la carta número 1 fuera. Nos quedan 4 cartas, así que para encontrar la siguiente, la carta número 2, vamos a necesitar 4 segundos. Cuando la quitemos, nos quedarán 3 cartas (3 segundos), luego 2 cartas (2 segundos) y vamos a poner 1 segundo más para la última, la número 5. En este escenario pesimista habremos necesitado en total:

5 + 4 + 3 + 2 + 1 = 15 segundos.

Es poco, pero ¿y si tuviéramos más cartas que ordenar? Por ejemplo, para 20 cartas necesitaríamos más tiempo. En concreto:

20 + 19 + 18 + 17 + ... + 1 = 210 segundos.

Eso ya son 3 minutos y medio. Lógico: cuanto más cartas, más tiempo. En general para un número N de cartas tendríamos que calcular la suma:

N + (N-1) + (N-2) + (N-3) + (N-4) + ... + 1.

Con letras también se pueden hacer cuentas (es eso del álgebra y los polinomios y esas cosas del instituto). De hecho, la expresión anterior se puede simplificar, porque corresponde a una progresión aritmética y da al final

(N2+N)/2.

Ahora no vamos a ponernos aquí a repasar cómo se hacía esto de las progresiones. Para el caso, lo que nos interesa es que se trata de un polinomio en N (en el instituto casi siempre se usaba la letra x para los polinomios, pero vamos, que es lo mismo). Si cambiamos la N por 5 cartas, nos sale (N2+N)/2 = (52+5)/2 = 30/2 = 15 segundos y, si cambiamos la N por 20, nos da (202+20)/2 = 420/2 = 210 segundos. ¡Bien, todo cuadra con lo de antes!

Como la expresión (N2+N)/2 que nos da el tiempo de este método 1 es un polinomio, se dice que es un algoritmo de tiempo polinomial.

Método 2: Otra forma de ordenar las cartas (supongamos, como antes, que tenemos 5 para empezar) es simplemente barajarlas y probar si tenemos suerte, y que justo se nos hayan quedado ordenadas del 1 al 5. La verdad es que eso sería mucha casualidad. Si no salen en orden a la primera (como es de esperar), podemos volver a barajar y probar suerte otra vez. Y así hasta que suene la flauta. Para hacer las cuentas del tiempo que tardaríamos, vamos a suponer que nos lleva 1 segundo barajar y que además cada vez que barajamos sale una ordenación distinta. Por ejemplo, una vez puede salir el orden 2-3-5-1-4, a la siguiente el orden 4-5-2-1-3, luego 1-2-3-5-4 (uy, casi), etc... Y, como somos muy pesimistas, vamos a ponernos otra vez en el peor de los escenarios. Supongamos que nos salga la configuración 1-2-3-4-5 al final, tras haber probado todas las demás opciones. Uf, ¿y cuántas ordenaciones de la forma ××-×-×-× hay? Pues en el primer hueco × podemos poner 5 posibilidades (cualquiera de los 5 números posibles); en el segundo, 4 (si hemos puesto, por ejemplo, el 2 en el primer hueco ya solo nos quedan 4 opciones: 1, 3, 4 o 5); en el tercero, 3; en el cuarto, 2 y en el quinto, 1 (el número que nos quede). En total hay que multiplicar las posibilidades para obtener todas las combinaciones posibles:

5·4·3·2·1

Esto se puede escribir como 5!, donde el signo ! se lee factorial (y sí, son las famosas permutaciones de 5 elementos del instituto). En fin, que, si hacéis las multiplicaciones de arriba, os van a dar 120 segundos (2 minutos). Este método 2 es peor que el método 1 (2 minutos frente a 15 segundos para 5 cartas), pero bueno, dos minutos tampoco es tanto, ¿no? Pero si en vez de 5 cartas tenemos N cartas, tardaremos N! segundos. Por ejemplo, para el mazo de 20 cartas de antes (3 minutos y medio en el método 1) tardaremos ahora

20! = 20·19·18·17·16 · ... · 1

¿Cuánto es eso? Pues, en notación científica (uf, otra vez a hacer memoria de las clases del instituto), eso es, más o menos,

2,4·1018 segundos

¿Y para los que no son fans de la notación científica? ¿Eso es mucho? Pues un poquito: unas 5 veces la edad del universo, o sea, miles de millones de años. ¡Ni aunque hubiéramos empezado a barajar justo con el Big Bang, habríamos conseguido ordenar las 20 cartas! Es verdad que nos hemos puesto en el caso más desfavorable y que a lo mejor resulta que a la mitad nos aparece ya la ordenación buena. En cualquier caso siguen siendo miles de millones de años... Aunque siempre puede ocurrir que baraje la persona con más suerte del mundo y que justo a la primera... ¡bingo!, del 1 al 20 en un segundo. A ese ser con suerte sobrenatural los matemáticos le llaman máquina de Turing no determinista y, como os podéis imaginar, en realidad no existe, es solo una entelequia. Lo que está claro es que para el común de los mortales N! es un tiempo que nada tiene que ver con la expresión polinomial del rápido método 1. Por el contrario, este nuevo método 2 requiere un tiempo no polinomial (salvo para la envidiable máquina de Turing no determinista que podría resolverlo en tiempo polinomial). Se dice que este algoritmo es del tipo NP (del inglés: Non-deterministic Polynomial time). Los algoritmos NP son lentísimos –en seguida sobrepasamos la edad del universo–, pero, una vez que tenemos la solución, son fáciles de comprobar: en un abrir y cerrar de ojos cualquiera podría comprobar que la ordenación encontrada por la perfecta máquina de Turing no determinista es la correcta: 1, 2, 3, ..., 20.

En fin, que podemos olvidar del lentísmo método 2 y quedarnos con el método 1, mucho más eficiente. Podemos decir entonces que el problema de ordenar una baraja de cartas puede resolverse en tiempo polinomial (gracias al método 1) y referirnos a él como a un problema del tipo P.

Suerte que se nos ocurrió el método 1 ¿no? Pero eso no siempre sucede. Hay otros problemas para los que nadie ha dado con un algoritmo de resolución en tiempo polinomial; solo sabemos de ellos que pueden ser virtualmente resueltos en tiempo polinomial por máquinas de Turing no deterministas, pero eso en la práctica no se puede hacer, porque las máquinas de Turing no deterministas ya dijimos que son entelequias. Estos problemas se dice que están en la clase de complejidad NP. Y, aunque pueda parecer un lío, si lo pensáis bien, veréis que todos los problemas del tipo P son también NP, puesto que, si un simple mortal (o un ordenador real, que los matemáticos llaman máquina de Turing determinista) puede resolverlos en tiempo polinomial, no digamos ya la todopoderosa máquina de Turing NO determinista. Así que los problemas NP incluyen a los problemas P. La cuestión del millón de dolares es si el recíproco es cierto: ¿puede encontrarse un algoritmo rápido como el método 1 para cualquier problema NP y decir, por tanto, que todos los NP son también del tipo P?

Quizá el más famoso de los problemas NP es el del viajante de comercio. Se trata de una persona que tiene que pasar por una serie de ciudades de manera que tarde lo menos posible. Tiene el mapa con la posición de las ciudades y la distancia entre ellas. Así que una forma de resolver el problema es calcular todas las rutas posibles, ver cuántos kilómetros supone en total cada ruta y elegir finalmente la más corta. Pero, claro, ya sabemos que, si tenemos N ciudades, eso va a suponer que hay N! rutas y que eso da un tiempo no polinomial. Es el método 2 de antes. El asunto es que a día de hoy nadie ha encontrado un método 1 rápido. Ni siquiera se sabe si verdaderamente hay un método polinomial para resolverlo.

El problema del viajante de comercio tiene el interés de que es de los que se llaman NP-completo... ah...¿y eso qué quiere decir? Pues eso significa que todos los problemas NP que podamos imaginar pueden, en el fondo, transformarse en el problema del viajante. Así que, si a alguien se le ocurre un algoritmo de tipo polinomial para el problema del viajante, habrá demostrado que todos los problemas NP son en realidad problemas P, es decir, habrá demostrado que P=NP, y lo recompensarán por ello con un millón de dólares (y tal vez con la medalla Fields). O puede que no, que sea imposible encontrar un algoritmo polinomial. Si alguien demuestra que realmente es imposible, entonces

habrá demostrado que P≠NP y también le darán un millón de dólares (y tal vez la medalla Fields). En este último caso, podríamos olvidarnos de buscar una solución rápida al problema del viajante, porque no la habría.

Por último, para terminar de enredarlo todo un poco más, hay que tener en cuenta que hay problemas incluso más difíciles que los NP. Son problemas que ni siquiera una máquina de Turing no determinista puede afrontarlos con éxito. En fin, que no hay nada todopoderoso para las matemáticas.