P=NP: El cartel de cine más geek

Estrenada en 2012, Travelling Salesman es un “thriller intelectual” donde ocurre lo que muchos consideran impensable en ciencias de la computación: un grupo de matemáticos demuestra que P=NP. Como es “lógico”, los descubridores se verán ante el dilema de reconocer su hallazgo a pesar de saber que podría cambiar el mundo.

Realmente, la película pretende acercar al público lo mucho que la sociedad moderna depende de la tecnología y, sin que muchos se den cuenta, de matemáticas puras y duras. Un caso bastante bien conocido es la criptografía: cada vez que compramos por Internet, enviamos nuestros datos y número de tarjeta de crédito cifrados a través de decenas de enrutadores y servidores por medio mundo. Sólo gracias a un teorema matemático y la dificultad de realizar una “cuenta difícil” podemos estar tranquilos de que ningún intermediario puede descifrar esa información.

Cartel de cine (Fuente)

Cartel de cine (Fuente)

La clave está en que cifrar o descifrar un mensaje es algo sencillo conociendo la clave, pero es muy difícil sin ella. Para los científicos de la computación, forma parte de lo que se llama familia de algoritmos de complejidad P, por tiempo polinómico. Resumiendo mucho, por otro lado encontramos algoritmos con complejidad NP, a los que es extremadamente difícil encontrar una solución pero muy fácil verificar si una solución es válida una vez dada. Por ejemplo, colocar una serie de paquetes en una mochila para que la rellenen completamente, dejando el mínimo de huecos, es extremadamente difícil. Pero si te la dan ya rellena, es trivial verificar que todo está bien empaquetado.

A día de hoy, nadie sabe si los problemas de NP se pueden convertir en problemas de tipo P de alguna manera. Las implicaciones de que sí se pudiera serían enormes, tanto positivas como negativas. Empezando por lo malo, toda la seguridad informática basada en criptografía podría tambalearse (dependiendo del tipo de hallazgo), con lo que eso implicaría en escuchas de teléfonos móviles, comunicaciones por Internet, acceso a datos cifrados, etc.

Aún así, es posible que las supuestas ventajas fueran aún más destructivas: casi todos los algoritmos que frenan el avance de la inteligencia artificial son NP-completos, por lo que todo lo relativo a máquinas que analicen y aprendan del mundo entraría en una edad de oro. Se verían afectados desde el estudio del plegado de proteínas para tratar cáncer hasta el diseño de nuevos métodos de especulación en los mercados financieros o drones de guerra más inteligentes y autónomos.

¿Merecería la pena vivir en un mundo donde P=NP?

Si te gustó, ¡compártelo!

Publicado en Humor, Programación Etiquetado con:
  • maroto

    Tienes el título mal puesto, es P=NP y no N=NP

    😛

    No he entendido mucho de lo que implica, pero voy a ver si puedo encontrar la película para entenderla mejor .
    Un saludo.

    • Jose Luis Blanco

      Gracias. Ambas cosas (la errata del título, y que no se entienda mucho) quieren decir… ¡que no debo escribir posts con tanta prisa! 😉
      Saludos.

  • No sé por qué, me ha recordado a otro tipo de problemas, aquellos a los que en principio buscamos una solución compleja y sofisticada, pero que tienen soluciones digamos… “inaceptablemente simples”.
    El caso mas conocido fue el que llevó a la NASA a gastar una ingente cantidad de dinero para diseñar un bolígrafo que pudiese escribir en el espacio con gravedad cero. Los rusos usaron un lápiz.

  • Diego Lopezosa Përez

    Me llamo Diego Lopezosa Pérez, he creado durante los últimos 10 años una nueva anatomía, por así llamarla,sobre grafos. Esta nueva morfología que se desprende de mi nueva idea lleva asociados dos algoritmos que creo atacan de forma satisfactoria el enigma del VENDEDOR VIAJERO.
    el nuevo enfoque trata a caminos eulerianos y hamiltonianos como casos particulares de un único concepto, unificando así en un mismo marco las clases P Y NP. Si alguien tiene a bien ponerse en contacto conmigo para tratar el tema, mi correo es: diegolopezosa@hotmail.es

    • Jose Luis Blanco

      Hola Diego,

      A pesar de que, sinceramente, me da cero confianza la manera falsamente científica en que describes tu “solución”, te he aprobado el comentario sólo para responderte: Si tan buena es tu solución, ¿la habrás enviado a alguna revista científica de revisión por pares, verdad? En ese caso, déjanos por aquí la cita para que podamos aprender.

      Un saludo.

  • Diego Lopezosa Përez

    Antes de nada, gracias Jose luis por aprobarme el comentario y tener la gentileza de escribirme. Dices que, si tan buena es mi “solución”… Si te fijas, digo en el comentario que, CREO, atacar de forma satisfactoria el problema…, no afirmo tener la solución. Como es lógico el método empleado ha de ser revisado por expertos, aun no lo he enviado a ninguna revista, pues mi trabajo es un manuscrito y he de informarme cómo darlo a conocer para no ser rechazado por falta de forma.
    En realidad, Jose luis, el estudio trata sobre una nueva concepción de aquello que constituye un grafo, (no voy a entrar en detalles hasta que no sea enviado a una revista y registrado en la cámara de la propiedad intelectual) pero sí esbozaré aquí, si lo tienes a bien, a grandes rasgos la idea general en que me baso.
    Cuando dije anatomía del grafo, tal vez no empleé la palabra adecuada (es solo un modo de referirme a la morfologia). Sabemos que están formados por dos elementos: puntos o vértices y,líneas o aristas que los unen. Si podemos pasar una sola vez por cada arista y regresar al vértice de salida decimos que el grafo es euleriano y si conseguimos visitar todos los vértices una sola vez y regresar al de inicio, será un ciclo hamiltoniano. Aristas y vértices mantienen separados y distinguidos ambos tipos de recorridos.
    En el trabajo que desarrollo, el grafo se concibe de otra manera distinta a la clásica, de modo que no se contemplan las aristas y vértices como hasta ahora, sé que esto puede sonar rarísimo porque vértices y aristas son los dos pilares que conforman el grafo y son una herramienta fundamental en matemática discreta con prestaciones incuestionables y resultados contrastados. Así es, pero sin desmentir todo esto,
    los grafos no estarían constituidos por puntos y líneas,(que es lo que intento demostrar en mi estudio) sino de otra forma ¡aun más sencilla! y que describo en mi teoría a la que he dado en llamar, Teoria de la Fusibilidad (TF).
    Gráficamente, la TF, no admite la existencia del vértice como tal punto. Como el vértice o punto en geometria ha dado tanto avance en matemáticas y física, se le da un voto de confianza de forma automática a la hora de abordar nuevos enigmas,pero , según mi parecer, el concepto de punto(que tan bien ha venido funcionando)no puede tener ya ese voto para otros retos. Pondré un ejemplo, en física durante cientos de años las leyes de Newton han funcionado y se ha contrastado su veracidad con la experiencia, ello hizo que se le otorgasee tambien el voto de confianza del que hablo a la hora de atacar nuevas preguuntas, pero se tuvo que abandonar esas leyes porque no conseguían explicar otros fenómeos. Las Nuevas leyes no desmentian las de Newton, solo las trataban como casos particulares, límite o completables, de este modo la mecánica cuântica o la relatividad consiguieron abrirse paso y dar respuesta a lo que la física newtoniana por sí misma y con todo su poder no conseguía.
    Para la TF, los recorridos euler. y hamilt. son solo casos particulares de un mismo tipo de recorrido, no distingue entre uno y otro,(como creo demostrar en el trabajo) del mismo modo que el cuadrado o el rectángulo son casos particulares dentro del marco único de los paralelogramos, por ejemplo. Vuelvo a repetir que todo esto da, como bien dices Jose luis, cero confianza, pero es solo porque al intentar imaginarlo se tiende a pensar nuevamente en términos de líneas y puntos que las unen.
    Gracias por haber leido hasta aquí y quisiera, si fueses tan amable tú que entiendes seguro de esto de las publicaciones, forma, y revisiones, me orientases, (si quieres claro) sobre el modo correcto de dar a conocer el trabajo.
    Un abrazo Jose Luis,gracias por tu paciencia y consejos y quedo a tu disposición.