Hola a todos, estaba haciendo un trabajo sobre este tema, y me parece tan interesante que quiero compartirlo con vosotros.
Os comento resumidamente.
Supongo que todos alguna vez hayamos escuchado hablar de este problema, o hemos leído en alguna web la pregunta "¿P = NP?. Pero, ¿qué es P?, ¿qué es NP?
Bien, imaginemos el conjunto de los problemas resolubles por un computador (algunos problemas no son resolubles). Muchos de estos problemas, los problemas P, se pueden resolver en un tiempo razonable (tiempo polinomial) con los computadores actuales, como pueden ser, por ejemplo, calcular el cuadrado de un número o encontrar el individuo de más edad dentro de un red social. Sin embargo existen tambien problemas, los problemas NP, para los cuales no se conoce una solución efectiva (la mejor es de tiempo exponencial), como el famoso problema del viajante de comercio, o la búsqueda de la clave de un criptosistema.
Algunos estaréis pensando qué diablos estoy contando aquí. Otros quizás más perspicaces, y al leer la palabra criptosistema saben por donde van los tiros. El caso es que los matemáticos no han podido aún demostrar si P = NP (por lo cual existirían métodos más sencillos de resolver esos problemas complejos) o P != NP (por lo cual no existirían).
¿Qué pasaría si P = NP? Si P = NP se puede demostrar matemáticamente que cualquier problema NP se puede resolver en tiempo eficiente, y de dicha demostración se derivarían automáticamente dichos métodos de resolución.Para el mundo de la criptografía las consecuencias serían fatales. La seguridad de los criptosistemas actuales de clave pública radica, entre otras cosas, en que los métodos para calcular dicha clave forman parte de los problemas NP, por lo tanto no son resolubles en un tiempo polinomial. Si P = NP cualquiera podría calcular dichas claves de forma relativamente fácil, y la seguridad en internet se vería gravemente comprometida. Recuerdo las clases de mi profesor de complejidad y computabilidad, en las que nos contaba a sus alumnos que aquél que se arriesgase a hacer público este conocimiento podría encontrarse rápidamente con los servicios de inteligencia entrando por su ventana. Más ahora con el tema de WikiLeaks y los supuestos cables que circulan de forma cifrada como seguro de vida de Julian Assange entre otros. Supongo que mi profesor exageraba, pero quién sabe. Aún así los avances en criptografía cuántica podrían dar una segunda oportunidad a todos aquellos que depositaron sus esperanzas en la criptografía de clave pública.
Estos inconvenientes nos hacen pensar que tal vez sea positiva la incertidumbre que existe sobre el problema, o una demostración que evalúe a falso la igualdad, pero lo que ganaríamos si P = NP es sorprendente.
Todos los problemas computables tendrían una solución eficiente. Problemas como el del viajante de comercio, de vital importancia para el transporte de mercancías, sería de uso trivial por todo tipo de compañías y agencias. Las redes sociales tendrían a su mano una poderosa herramienta para encontrar personas con gustos similares, o se podrían encontrar, en cuestión de milésimas, miles de artículos relacionados con una palabra clave, ahorrando esto no sólo recursos naturales, estructurales o tecnológicos, sino aparcando para siempre la laboriosa tarea de etiquetado “tags” de temas, crucial para el correcto asentamiento de la web semántica. Y esto es sólo el principio.
En el mundo de la Inteligencia Artifical el impacto sería tambien muy positivo. Encontrar el algoritmo más eficiente para tareas como el reconocimiento del lenguaje, reconocimiento de patrones visuales, predicción de sucesos, y otras tareas sería trivial.
P = NP tendría también grandes implicaciones en el mundo de las matemáticas. La demostración automática de teoremas se hará accesible en su totalidad para la capacidad computacional de los computadores actuales, de manera rápida y eficaz. Tanto es así que la persona que lograse demostrar P = NP no sólo se haría con el millón de dolares otorgado por el Instituto Clay relativos a este problema, sino con todos los restantes.
Pero no empecemos a soñar. El mundo de la criptografía puede respirar tranquilo por el momento, ya que, en general, los expertos creen que P != NP.
¿Cuáles son las alternativas que tenemos para resolver problemas de modo eficiente?
Los explicaré muy brevemente, y si alguno os interesa en especial lo comentaré en otro hilo de este foro.
Computación cuántica, que utiliza algunas propiedades fundamentales del mundo microscópico que, traducidas correctamente a operaciones matemáticas, son capaces de resolver problemas. Algunas de estas propiedades encierran también muchos misterios en sí, como la correlación de pares EPR, por la cual dos partículas, cualesquiera del universo, están de algún modo conectadas, de modo que si modificamos una de las dos, la otra se ve también alterada. Hay quien dice que debido a esto un gemelo puede sentir aquello que acontece a su otro gemelo. (Lo veo más bien raro).
Computación celular basada en membranas. La idea es utilizar células como si se tratasen de un computador. Algunas de las operaciones básicas que realiza una célula se pueden traducir a operaciones matemáticas, de modo que codificando en términos celulares nuestro problema, y en el entorno adecuado, podemos resolver problemas. Esto es muy interesante, no tanto por la velocidad de cálculo de una célula, sino por la cantidad de células que pueden trabajar en tiempo paralelo a escala muy reducida. Todo el mundo sabe que un trabajo paralelizable se hace más rápido cuantás más personas intervengan en él.
Computación molecular con ADN. La idea en este caso es la de utilizar moléculas de ADN, y sus operaciones de división, unión, etc, para resolver problemas, al igual que en el caso anterior. Esto, a diferencia de lo anterior, no es sólo una posibilidad teórica, sino que ya se ha hecho en laboratorios. (Véase el experimento que Leonard Adleman realizó en 1994).
Un saludo a todos, y perdón por el tostón. Es un tema que me resulta muy interesante y que me gusta darlo a conocer.
:
(pista).
![[sonrisa]](/images/smilies/nuevos/risa_ani1.gif "sonrisa")
