últimos mensajes de: Machacador

El problema del milenio "P vs NP" bien destripado, para legos.

Si hay algo que caracteriza normalmente a los problemas matemáticos del milenio, es no solamente la dificultad que entraña su resolución, si no también, la simple comprensión de su enunciando…obvio, hablamos de problemas por los que se paga un millón de dólares y que aún siguen abiertos; ciertamente son cosas para los profesionales. Sea como fuere, uno de ellos, el P versus NP, rompe un poco con la regla general, y no lo digo por la dificultad de su resolución, que es brutal, sino porque el enunciado es fácilmente comprensible y fácilmente abordable por el lego. Además, la ganancia de su resolución no es simplemente el millón de dólares, hay mucho más detrás de ello; el genio que diera con su solución, en caso de que ésta fuera positiva (ya veremos qué significa esto), sería el amo del mundo, y no me refiero a que podría descifrar determinados sistemas de cifrado, no, eso se dice normalmente y es una majadería, de hecho yo no perdería el tiempo en eso, el caso es que tendría un poder de cálculo en sus manos tan asombroso, que por ejemplo, podría tener de primera mano poderosas predicciones de bolsa antes que nadie… vamos a ello.

Voy a explicarlo mascado, mascado, mascado…y riguroso, porque se puede.

Imagínate que nos dan este conjunto de números A = { -2, 12, -1, -1, 5, 6} y nos piden que seleccionemos aquellos números del conjunto, tal que al sumarlos, obtengamos el número 2.

Por ejemplo, si cojo el -2, el 5 y el -1, estos suman -2+5-1=2.

Técnicamente hablando, esta preguntan es la mismita que: ¿existe en el conjunto A, algún subconjunto cuyos miembros suman 2? Sí, sí existe, es {-2, 5, -1}

Bien, ahora nos preguntan ¿y 17?, ¿existe en este conjunto A de números, un subconjunto que sume 17?, le echáis un vistazo y…sí…por ejemplo el 12 y el 5 suman 17, por lo tanto {12, 5} sería el subconjunto buscado.

¿Y -1?, sí, el propio {-1} es un subconjunto cuya suma es -1, por supuesto.

¿Y 4?, para 4 hay varias soluciones como {5, -1}, y también el {6, -2}, pero como nos preguntan si existe alguno, bastaría con decir que sí y mostrar uno de ellos.

¿Y 0?, ¿hay algún subconjunto en él que sume cero? mmmm…no, parece que no hay ninguno...

Este problema, llamado “Subset sum Problem”, que así planteado parece de chichinabo, es, en resumen, uno de los problemas al que pueden reducirse los más complejos dilemas involucrados en la logística o trasportes de las grandes empresas, más adelante entenderemos porqué, pero de momento nos basta con saber que si tuviéramos una solución general y eficiente para este problema, nos serviría para otro tipo de problemas del que dependen millones de euros. Así que sigamos.

Cuándo nos piden que busquemos un subconjunto que sume X en este conjunto A de seis números, ¿qué hacemos? Lo que hacemos es empezar a mirar entre los números y mentalmente vamos probando sumas hasta que encontramos lo que buscamos, también, en realidad, aprovechamos nuestra experiencia en sumar para descartar los números grandes o pequeños dependiendo de la suma, pero en definitiva vamos a prueba y error.

Imaginad, pues, que en una de estas importantes empresas, nos piden que realicemos un programa informático para resolver este tipo de problema; se trataría de un programa al que se le pasará un conjunto de N números entre positivos y negativos, y también la suma que buscamos, y éste nos dirá si existe tal subconjunto (dando un resultado válido), o si no existe tal subconjunto. Es decir, si a nuestro programa le pasaran el conjunto de números del ejemplo, A, y que la suma que buscan es el 2, el programa devolvería {-2, 5, -1}; y si le pasaran A indicando que la suma que buscan es 0, nuestro programa devolvería, por ejemplo “no existe tal subconjunto”.

¿Cómo haríamos este programa? Lo primero que viene a nuestra mente sería hacer un programa que buscara todas las combinaciones, que resolviera todas las sumas posibles que se pueden hacer en el conjunto dado, hasta encontrar el resultado que se busca; en cuanto encontrara uno, ya podría decir que existe tal subconjunto y devolverlo, y en caso de agotar todas las combinaciones sin encontrar la suma, devolvería un “no existe tal subconjunto”. Es decir, si le pasaran el conjunto A de nuestro ejemplo, y tuviera que buscar si existe un subconjunto que sume 2, nuestro programa empezaría a probar primero a ver cada número por separado por si alguno fuera el 2, como ninguno lo es, empezaría a coger parejas y a sumarlas (12-2=10, -1-2=-3…) al no encontrar ninguna que sume 2, empezaría con los tríos (-2+12-1=9, -2+12+5=15…), y entre los tríos encontraría -2+5-1=2 y ahí pararía y devolvería {-2, 5, -1}.

¿Y si le preguntáramos por el cero? pues miraría cada número, después las parejas, después los tríos, después los cuartetos…etc., hasta completar todas las combinaciones; no encontrando ninguno que sume cero, devolvería que “no existe tal subconjunto”. Fijémonos en este caso donde ha tenido que mirar todas las combinaciones ¿Cuántas son? En el caso del conjunto A, que tiene 6 números (6 elementos), las combinaciones de parejas, trios, cuartetos… etc., en total, son {2}^{6} - 1 combinaciones que tendría que mirar.

Un conjunto de N elementos, tiene{2}^{N}combinaciones posibles. Veámoslo con un conjunto de 3 elementos {a,b,c}, las combinaciones son {0,a,b,c,ab,ac,bc,abc} (el 0 que aparece en el conjunto de combinaciones es el conjunto vacío, el cual se incluye siempre por convenio, es decir, una de las combinaciones es no tener ninguno; para lo que tratamos ahora, es irrelevante; si quitamos el conjunto vacío, las combinaciones son{2}^{N} - 1como en nuestro ejemplo ).

Esto quiere decir que si a nuestro programa le pasaran un conjunto de N números, en el peor de los casos, si tardara un segundo en hacer cada suma (un ordenador es mucho más rápido, este ejemplo es solo para entendernos) tardaría en darnos una respuesta{2}^{N}segundos. Lo cual, aunque no lo parezca es un problema, porque si se trata de 10 números, tira qué te va, pero si se trata de 100 números... ¡ah!, {2}^{100}ya son palabras mayores, este es un tiempo intratable.

Si un algoritmo, un programa, tiene que dar{2}^{N}pasos (de forma general {k}^{N} pasos) para resolver un problema en el peor de los casos, decimos que tarda un tiempo EXPONENCIAL (en realidad no importa el tiempo que tarde en dar cada paso, ya sea un segundo, o un milisegundo o menos); y un tiempo exponencial es problemático.

En general, un algoritmo que tenga que dar {k}^{N} pasos, donde N es en número de datos de la entrada que tenemos que tratar, es terrible, basta con que N aumente un poco, para que el número de pasos se dispare, y con él, el tiempo.

Acordaros de aquella leyenda del rey, que ofrece al inventor del ajedrez que pida la recompensa que quiera por dicho invento, y el buen hombre, ni corto ni perezoso, pide que pongan en el primer cuadrado del tablero de ajedrez un grano de trigo, en el segundo, dos granos, en el tercero, cuatro, en el siguiente ocho, y así cada vez el doble; el rey pensó que semejante regalo era una ridiculez y aceptó…pero no se percató que{2}^{63}son aprox. 276600 millones de toneladas, muchísimo más que la producción anual, actual, de trigo en todo el planeta (ref: http://dunia.somms.net/?p=12)

Fijaros entonces que no importa lo rápido que sea nuestro ordenador, es decir, que si tengo un determinado algoritmo, programa de ordenador, al que le voy a pasar N datos, y para darme la solución tarda{k}^{N}, el hecho de que tengamos un superordenador cuántico de la muerte no nos va a ayudar mucho, por que podría hacer que para N= 1000 tarde solo unas horas, pero si resulta que quiero resolver un problema con N=1500, entonces serán días, y N=5000 ya será intratable…Y recordad que a este problema se reducen problemas muy importantes como la planificación y logística de grandes empresas, la fabricación de microchips, la ordenación de las ciudades o de redes de transportes, la secuenciación del ADN… y un largo etc…¿os imagináis cual será el valor de N en estos casos? Seguramente, esto que os digo, lo habréis escuchado (o leído en la Wikipedia) sobre el dilema del Viajante… pues sí, el “Subset sum problem” es exactamente del mismo tipo.

Por lo tanto EXPONENCIAL = caca de la vaca.

Vamos llamar, a partir de ahora al “Subset sum problem”, el problema SSP.

Sigamos pues con el programa que nos han planteado hacer. Acabamos de ver que si miramos todas las combinaciones, en el caso de que nos pidan una suma cuyo subconjunto no exista o en caso de que la solución esté por el final de las combinaciones a mirar, el algoritmo es intratable. Por lo tanto debemos modificarlo.

Para esta modificación, lo ideal sería encontrar algún atajo matemático; suponte que basta con sumar los N números que nos pasan, dividirlo por el número X cuya suma buscamos, y después de varias operaciones obtenemos los dígitos del subconjunto esperado, o un resultado del que se infiere que este subconjunto no existe; supón que los pasos del algoritmo fueran2{N}^{3} + 5; este número de pasos ya es tratable; N puede aumentar mucho sin que se note especialmente en el número de pasos. Cuando esto ocurre decimos que tiene un tiempo POLINÓMICO. Fijaros en la diferencia, el número de datos a tratar N, no es exponente, está en la base, esta es la diferencia más fundamental.

Un tiempo del tipo {N}^{k} + a es ideal, es POLINÓMICO y perfectamente tratable por un ordenador. Cuidado que si el polinomio es tal que N aparece como factorial (N!), entonces es más terrible que el exponencial; por lo tanto será polinómico siempre y cuando no solamente N no sea exponente, si no también que no esté como factorial o cualquier otro tipo de barbaridad semejante.

Por lo tanto POLINÓMICO = mola mucho.

Algunos os preguntaréis si no es un término vago eso de los “pasos”, y sobre todo, si está definido eso de “algoritmo” o “programa informático”; existen matemáticas detrás de estos términos que lo hacen bastante riguroso; cuando se habla de programa de ordenador es perfectamente lícito imaginar un programa en Linux o Windows, pero matemáticamente hablando nos referimos a máquinas de Turing. Es decir, que hay cierta construcción matemática detrás, si bien, también hay mucho predicado de segundo orden e intuición, como en la topología o el análisis.

Vamos a entrar ya en materia.

En complejidad computacional existen infinidad de siglas para indicar niveles de complejidad a la hora de solucionar problemas, y de esta forma los propios problemas se van organizando. Entre todo este increíble zoo de siglas, hay dos muy famosas, los problemas de tipo P, y los problemas de tipo NP.

Los problemas de tipo NP son aquellos, tal que si se nos diera una posible solución afirmativa, nosotros podríamos decir si la solución es buena o no en un tiempo polinómico. Vamos a entenderlo con nuestro ejemplo.

El problema SSP es de tipo NP, veámoslo: a alguien le hemos pasado nuestro conjunto A, y le hemos preguntado si existe en él, algún subconjunto que sume 2. Esta persona lo busca y nos dice que sí (solución afirmativa), dándonos esta solución {-2, 5, -1} ¿Cuánto tiempo tardaríamos en comprobar si la solución es buena? Prácticamente nada, solo tendríamos que sumar los números del subconjunto y ver que suman 2...esto se hace en un tiempo polinómico, en este caso concreto, dos sumas (sumar -2+5=3 y después 3-1=2), dos pasos; veríamos que suman 2 y responderíamos que la solución es buena. Y si con la misma pregunta nos pasara el {-1, 5}, pues los sumaríamos (un solo paso) y responderíamos que no es buena. Un programa informático que comprobara si las soluciones afirmativas (nos pasa un subconjunto) son buenas o malas en nuestro ejemplo, tardaría un tiempo polinómico en responder, pues en el peor de los casos podría pasarnos como solución el conjunto entero, por lo que solo tendríamos que hacer 5 sumas, es decir, 5 pasos. De forma general N-1 pasos…polinómico. En cambio si la respuesta fuera negativa , es decir, si nos dijera que no existe tal conjunto, comprobarlo ya no tendría por qué llevarnos un tiempo polinómico. He aquí por qué es NP.

Este tipo, el NP, puede parecer una forma rebuscada de clasificar problemas, pero nada más lejos de la realidad ¿Qué es lo primero que se nos ha ocurrido a la hora de hacer un programa informático que nos diera el subconjunto correcto; que resolviera el problema SSP?, lo primero que se nos ha ocurrido es ver todas las soluciones, ¿por qué? Porque rápidamente nos hemos percatado que comprobar cada posible solución era rápido, por lo tanto parecía razonable ir viendo soluciones en orden hasta dar con la buena. La contrariedad es que las soluciones a buscar son tantas, que a pesar de que cada comprobación es polinómica, en su totalidad, dar con la solución buena es exponencial.

Pensad cómo resolvemos problemas en la vida normalmente; de forma instintiva lo primero que hacemos es pensar rápidamente si comprobar la bondad de soluciones es rápido, y si es así, en vez de ir al fondo de la cuestión, lo cual puede ser lento y tedioso, preferimos rápidamente ir descartando candidatos; pensando en posibles alternativas, en posibles soluciones, vamos probando si son buenas o no; además, estas candidatas que nuestra mente va sacando no son aleatorias, más o menos vamos seleccionando lo más probable, y solo, en el caso de que no haya forma de dar con la buena, abandonamos el método e intentamos llegar al fondo de la cuestión.

El problema SSP es un problema de tipo NP, del cual no se conoce ninguna solución exacta polinómica; las únicas soluciones exactas que se conocen tardan un tiempo exponencial, pero existen problemas de tipo NP que sí se pueden resolver en un tiempo polinómico. Por ejemplo, el problema de los compañeros de cuarto: si se nos diera una lista de N estudiantes, tal que debemos de emparejarlos, y una lista con las preferencias de cada uno, entonces, existe un complejo algoritmo que es capaz de hacer esta faena, de la forma más óptima, en un tiempo polinómico. También, si tenemos dos secuencias de ADN, y queremos saber el menor número de inserciones o borrados que tenemos que hacerles para que sean iguales, aun siendo un problema NP, puede resolverse en un tiempo polinómico.

Ahora veamos cuales son los problemas de tipo P; estos son aquellos que pueden resolverse en un tiempo POLINÓMICO. Eso es todo.

Por lo tanto, el problema de los compañeros de cuarto, o el de la secuenciación de ADN, son problemas de tipo P, y también de tipo NP, pero el problema SSP solo sabemos que es de tipo NP, no sabemos si es de tipo P.

Antes de recapitular, tenemos que decir también que todos los problemas de tipo P, son NP, es decir, que si un problema puede resolverse en tiempo polinómico, siempre será posible poder comprobar sus resultados afirmativos en un tiempo polinómico. Dicho de otra forma, es posible tanto tener un algoritmo eficiente para solucionarlo, como el tenerlo para comprobar si un determinado resultado positivo es bueno o no.

Resumamos: Con lo visto podemos inferir que el conjunto de los problemas NP contiene tanto a todos los problemas de tipo P, como otro tipo de problemas que desconocemos sí pertenecerán también al tipo P, como es el caso del problema SSP ¿Qué pasaría si estos problemas fueran también P? pues que entonces NP=P…y esto es lo que se pregunta el problema del milenio, el problema P vs NP, ¿es P=NP?

P versus NP = ¿Es P=NP?

Hemos dicho antes, que los más intrincados problemas de logística y planificación, podrían reducirse al problema SSP, ¿por qué? Porque este problema es de tipo NP-Completo.

Los problemas de tipo NP-Completo son todos aquellos que siendo de tipo NP, no solamente desconocemos si tienen solución exacta en tiempo polinómico, si no, además, todos ellos son equivalentes, y todo problema del tipo NP puede transformarse en ellos también; o sea, el problema del viajante es NP-Completo, y puede reducirse al SSP, y viceversa (podemos convertir uno en otro en un tiempo polinómico), y cualquier problema de tipo NP puede reducirse a ellos.

Por lo tanto, todo lo que se demuestre para los de tipo NP-Completo, se demuestra para el resto NP.

Esto quiere decir que si lográramos un algoritmo que solucionara el SSP de forma exacta y en tiempo polinómico, tendríamos solución para todos los problemas NP y por lo tanto estaríamos resolviendo el problema del milenio.

Repito: si encontráramos un algoritmo que tardara un tiempo polinómico en dar solución al problema SSP, estaríamos resolviendo el problema del milenio, pues valdría para todos los NP, y por lo tanto P=NP. Y quien dice SSP dice cualquier otro problema de tipo NP-Completo, por supuesto.

Si demostráramos que tal algoritmo para SSP no existe, habríamos resuelto que P es distinto a NP, que es la respuesta negativa al problema del milenio.

Tal vez os preguntéis, cómo hacen las empresas para resolver este tipo de problemas que no pueden resolverse hoy por hoy en un tiempo polinómico, y que necesitan darles solución diariamente. Existen algoritmos no exactos, de carácter probabilístico, que funcionan extraordinariamente bien, y es por ello que la posible solución exacta se ha relegado al mundo teórico, es tan compleja que no vale la pena invertir en ella…pero ¡ah, amigo!, si la respuesta es que P=NP, y das con el algoritmo mágico…madre del amor hermoso, yo no sé si sois conscientes de la importancia de tal hallazgo ¡Cuantos secretos del universo en vuestras manos!

¿Cómo está el asunto hoy en día? En primer lugar está casi descartado que pueda encontrarse una solución polinómica a alguno de los problemas NP-Completos; pues si tal solución existe, habrá de ser única y extravagante, lo cual hace imposible en la práctica que alguien se haga con tal joyita por puro azar o rompiéndose la cabeza. Los profesionales se dedican, hoy por hoy, a ir acorralando el problema en base a atacar otros grupos de complejidad, y al tiempo, en ir demostrando desde perspectivas más abstractas temas generales, como por ejemplo la imposibilidad de demostrar P=NP por métodos aritméticos o por ejemplo con relativización (que tan buenos resultados ha ido dando en la complejidad computacional).

Así que hay que currárselo, y mucho…

Espero de corazón que os sirva este artículo de referencia, y que os haya ayudado tanto como a mí me ha divertido escribirlo.

Fuente: http://e-ciencia.com/blog/divulgacion/el-problema-del-milenio-p-vs-np-bien-destripado-para-legos/