¿El problema más importante: P vs. NP?

[JonaLamper]

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 NP

Cuando 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 Problema

El 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 != NP

Si 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 = NP

Aquí 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:

• https://es.wikipedia.org/wiki/Problemas_del_milenio#P_versus_NP
• http://www.xatakaciencia.com/matematicas/p-versus-np-nunca-lo-entendiste

[A.I.]

NP no quiere decir no polinómico. NP es polinómico, pero no determinista.

[JonaLamper]

¿Has leído todo el thread? Me refiero sobre todo a la parte que dice "NP significa Polinómico no determinista".

Cuando digo que tarda un tiempo "no polinómico" me refiero a que los ordenadores tardan ese tiempo en resolver un problema en NP. O sea, tardan un tiempo exponencial (n^2, n^100...). Lo cual es "no polinómico"

[A.I.]

Las clases de complejidad P y NP
...

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).
...

A parte de que hay información errónea está muy mal redactado, lleva a confusión.

[JonaLamper]

Está bien, dime, ¿qué información errónea hay?

[A.I.]

Por ejemplo lo que he citado en el mensaje anterior.

[JonaLamper]

Te vuelvo a repetir: lo ordenadores de hoy en día son deterministas. No existen ordenadores con muchísimos cores tales que cada core pueda ir explorando una solución como si fuese una Máquina de Turing no determinista. Luego los ordenadores de hoy en día tardan un tiempo polinómico en resolver problemas en P y un tiempo no polinómico (o más técnicamente "súper polinómico) en resolver problemas en NP.

Si eso es lo que no se entendió, ahora queda solucionado.

[A.I.]

Entonces parece que tienes a mano la demostración de P != NP, cuéntanos que tal la entrega del premio. También es una pena que hayas conseguido demostrar la opción no rentable (económicamente) del problema

[JonaLamper]

Lo que es una pena es que no haya gente en este foro interesada en la cuestión de P vs. NP.

Porque es obvio que tú no cuentas.