Primero la imagen, y luego a hilar fino.

Cachis la mar, otra vez Futurama de las narices. Pero aunque la imagen no te diga nada…aquí estoy yo para aburrirte. La cosa es difícil (más incluso que la semana pasada, pero aparece algo que he aprendido en la carrera y eso me hace ilusión. Sí, sólo sirve para esto). En la parte de abajo de la librería aparecen dos tomos llamados P y NP; y si quieres ganar un millón de dólares…sigue leyendo ^_^
Resulta que uno de los (muchos) misterios de la humanidad está resuelto en esa imagen. El tamaño de los tomos P y NP es el mismo, lo cual es un guiño para construir una afirmación: P = NP
Si eres capaz de demostrarlo…habrás ganado ese millón de dólares. Y ahora vamos a explicar que es P y qué es NP, es complicadillo, pero me hace ilusión.
Si mal no recuerdo P era el conjunto de problemas que se pueden resolver en tiempo polinómico (digamos que eso significa que se pueden resolver de forma rápida sea cual sea la complejidad del mismo). Y NP son los problemas en los que podemos ver si una solución es acertada(comprobar) en tiempo polinómico, pero no sabemos resolver el problema en dicho tiempo.

• Problema: Dos números que suman 5
• Resolver el problema sería encontrar dos números que solucionaran el problema, por ejemplo 1 y 4.
• Comprobar el problema sería, a partir de una solución, por ejemplo 2 y 3, ver que resuelven el problema. En este caso es verdad

Este es un ejemplo muy sencillo por el que no te van a dar un milloncico de dólares, pero ¿a que te cuesta más encontrar dos números que sumen 23, que comprobar que 22 y 1 suman 23?

Por cierto, hasta ahora sabemos que P está dentro de NP (si puedes resolverlo…seguro que también comprobarlo). Sólo hay que demostrar que si puedes comprobar un problema en tiempo polinómico también lo puedes resolver.

Fuente

Noticia de Miky