P vs NP, un problema complejo
(Programa 1)
En el año 2000, el instituto Clay propuso 7 problemas que serían conocidos cómo “Los problemas del milenio”. Hoy en día, sólo uno de esos 7 problemas ha sido resuelto. En Agosto de 2017, otro de esos problemas estuvo cerca de ser resuelto, pero finalmente se descubrió un error en la demostración. Dicho problema era conocido como P vs. NP, y su solución nos daría la respuesta a la siguiente pregunta: ¿Es lo mismo saber resolver un problema que saber reconocer una solución del mismo?
Dentro de la complejidad que asociamos a los problemas, hemos distinguidos dos grandes tipos de problemas. Decimos que un problema es tipo P si puede resolverse fácilmente, y decimos que un problema es tipo NP si podemos comprobar fácilmente si algo es solución de ese problema o no.
P = Se resuelve fácil.
NP = Se comprueba fácil.
Hoy en día, sabemos que todos los problemas P son NP, ya que si sabemos resolver un problema fácilmente, sabemos comprobar si algo es solución o no. Pero, ¿Y al contrario? Ahí está la cosa. No sabemos si todos los problemas NP son P o no.
¿Y qué tiene de especial?
Si resulta que P≠NP, podríamos estar totalmente seguros de nuestra ciberseguridad de hoy en día, pero si por el contrario, resulta que P=NP, nos cargamos toda la seguridad tal y como hoy la conocemos, pero a cambio, tendríamos una fórmula que nos permitiría combinar moléculas para, por ejemplo, curar el cáncer.
¿Quieres saber más? Escucha este podcast, que forma parte del programa “La Taberna”, y fue emitido el Miércoles 19 de Octubre de 2017 en OndaCampus. Además, también puedes responder a la pregunta de la semana pulsando aquí:
