premio3.png

P versus NP es uno de los siete problemas del milenio 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 sólo. 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 descubramos 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 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 segundas) y vamos a poner un 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 (era 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

Eso es 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.

cartas.jpg

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 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 (que es lo más normal) 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 sólo 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 va 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 sólo 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 que la perfecta máquina de Turing no determinista ha encontrado es la correcta: 1, 2, 3, ..., 20.

En fin, que creo que nos 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.

mapa.jpg

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; sólo 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 Field). 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 Field). 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.

 

REFERENCIAS:

K. Devlin. The Millennium Problems. Basic Books (2002)

https://en.wikipedia.org/wiki/P_versus_NP_problem

https://es.wikipedia.org/wiki/M%C3%A1quina_de_Turing#M.C3.A1quina_de_Turing_determinista_y_no_determinista

  • No comments found

Leave your comments

Post comment as a guest

0
Your comments are subjected to administrator's moderation.