Bueno, ahora explicaré un poco mejor qué es P vs. NP (espero que está vez no me borren el thread
) y porqué es el problema más importante en computación y uno de los más importantes del mundo. Vamos a ello:
Esta historia empieza cuando el Instituto Clay de Matemáticas (Cambridge, Massachusetts) se reúne en el año 2.000 y establece 7 problemas muy importantes cuya solución se desconoce. Estos 7 problemas pasan a conocerse como "Los problemas del milenio" y el Instituto Clay ofrece una recompensa de 1 millón de dólares por la resolución de cada problema. Como os podéis imaginar, el simple hecho de entender los problemas no está al alcance de todos, pues son problemas bastante profundos que tienen que ver con matemáticas, física, etc. Hoy vamos a conocer uno de ellos: P vs. NP. ¿Por qué? Porque P vs. NP es el problema más reciente de todos y resulta muy fácil de entender (y además es un problema de computación). Vamos a explicarlo sin entrar en muchos detalles y abordando lo básico para saber de qué trata:
Las clases de complejidad P y NPCuando logramos resolver un problema con un algoritmo tardamos un tiempo... el que sea. Nos vamos a concentrar únicamente en dos tiempos: polinómico y no polinómico. Los problemas que tardan un tiempo polinómico son aquellos que se resuelven en un tiempo n, n^2, n^3, n^100, n^10000, etc. Y los problemas que tardan un tiempo no polinómico son aquellos que se resuelven en un tiempo 2^n, 3^n, 10^n, 100^n, etc. Como todos sabéis, es mucho peor 2^n que n^2. Vamos a ver algunos problemas de ejemplo
- Ejemplo polinómico: imaginemos que queremos buscar un número en una lista sin ordenar. Entonces no queda más remedio que recorrer toda la lista, ¿verdad? Bien, pues ese problema se resuelve en un tiempo polinómico (pues a las malas tendremos que recorrer toda la lista).
- Ejemplo no polinómico: imaginemos que te doy un conjunto de números, este: {0, 2, 4, 5, 10, 230, 783, 45, 61, 17} y te digo "¿Hay alguna forma de que con ese conjunto consigas obtener el número 8 haciendo sumas y restas? Entonces lo que tú harías es empezar a probar todos los números a ver si logras el número 8 (ten en cuenta que el conjunto podría ser muy grande, de tamaño n).
Perfecto, ahora sabemos que existen 2 cajitas donde podemos clasificar los problemas según tarden un tiempo polinómico o no polinómico en resolverse. Pues estas dos cajitas son las clases de complejidad P (polinómico) y NP (no polinómico). Por cierto, P en realidad significa "Polinómico determinista" y NP significa "Polinómico no determinista", pero esto es otra historia que será contada en otro momento.
Vale, vale. Pero... ¿Y por qué todo esto es tan importante? Ahora mismo te vas a dar cuenta.
El ProblemaEl problema de P vs. NP se basa en demostrar si ambas clases de complejidad son la misma (en este caso P = NP) o son diferentes (P != NP). Dicho de otro modo: ¿existe algún problema en NP que pueda resolverse en tiempo polinómico? Pues aunque esta pregunta parezca tan trivial, nadie lo sabe. Vamos a ver qué pasa si P = NP o si P != NP (ahora sí que os vais a acojonar).
P != NPSi P != NP (que es lo que la mayoría de la gente piensa) en realidad no hay grandes cambios. O sea, esto no sería divertido. Simplemente se sabría que hay problemas cuya resolución no puede hacerse mejor que en tiempo no polinómico. Y poco más.
P = NPAquí viene lo divertido. Veamos: hay problemas que tardan tiempo no polinómico y entonces, cuando tienen una entrada un poco grande, la función crece rapidísimo (imagina 2^100 o 2^1000). Por lo tanto, aunque los ordenadores vayan súper rápidos, tardarían un tiempo muy, muy grande en hallar una solución. ¿Sabéis ese fabuloso algoritmo de cifrado que se llama RSA? RSA se utiliza para cifrar cuentas bancarias y multitud de comunicaciones hoy en día. Pues bien, RSA se basa en la factorización de números enteros, ¿y sabéis qué? Hallar la factorización de números enteros es un problema que está en NP. Luego, ¿os imagináis qué pasaría si alguien descubre que P = NP? Pues eso, que toda la seguridad de Internet se va a la *****.
No quiero extenderme mucho más, pero si buscáis un poco, veréis que hay miles de problemas en NP (y muchos de ellos con un gran impacto en el día a día del ser humano). Así que si P != NP perfecto. Pero si P = NP... Creo que no exageraría al decir que la vida cambiaría para muchas personas.
Y por eso, P vs NP es uno de los 7 problemas del milenio (y quizá el de mayor repercusión).
Aquí termina la historia y os dejo una pregunta para quien quiera resolverla:
¿P = NP o P != NP?
Links interesantes:
Mostrar Temas
¿Alguien recuerda algunos? Me refiero a juegos tipo el de la cadena de palabras (una persona dice una palabra, la siguiente dice otra palabra cogiendo la terminación de la palabra anterior, etc). Sé que hemos hecho bastantes, pero mi memoria a largo plazo es muy mala 
Estoy estudiando la librería Isotope con la que puedes filtrar, ordenar, etc.
