HomeP vs. NP: el "problema de un millón de dólares"
.jpg)
A comienzos del siglo, el Clay Mathematics Institute presentó los denominados Problemas del Milenio: siete problemas matemáticos de gran complejidad e importancia, cuya resolución aportaría grandes desarrollos y avances tecnológicos. Para alentar a mentes brillantes a que aborden estos problemas, se ofreció un premio de un millón de dólares. Entre los varios problemas enumerados, uno es de extrema importancia en el ámbito de la optimización: la pregunta de si P es igual a NP.
Retrocedamos un paso para comprender mejor lo que representan estas letras y esta ecuación. Para ello, podemos definir dos clases de problemas. Clase P (tiempo polinomial determinista), compuesta de problemas que se pueden resolver rápidamente, y en los que la dificultad crece lentamente con la dimensión del problema; y Clase NP (tiempo polinomial no determinista), cuyas soluciones se pueden verificar rápidamente. Por lo tanto, la pregunta es si cualquier problema cuya solución se puede verificar rápidamente también se puede resolver rápidamente.
Esta pregunta permanece sin respuesta debido al hecho de que aún no se comprobó que haya problemas cuya solución se pueda verificar rápidamente, sino que el descubrimiento de una solución no se puede determinar de manera eficiente.
Suponga que desea viajar por Brasil y visitar las 26 capitales de estado y el Distrito Federal. Al preparar el itinerario, se hace una pregunta: ¿es posible realizar este viaje cubriendo menos de 15 000 km? Es extremadamente difícil responder esta pregunta ya que se necesitaría probar todos los posibles órdenes de recorrido y calcular su distancia. No obstante, es muy fácil verificar si se puede cubrir un recorrido dado con menos de 15 000 km, ya que basta añadir la distancia entre las ciudades en el orden definido. Por lo tanto, este problema es NP, ya que se puede verificar rápidamente una solución, aunque aún no se sabe si también es P, ya que no se lo puede resolver rápidamente.
Una tercera e importante clase de problemas se denomina NP-completo: son problemas NP que se pueden transformar en otros problemas NP en tiempo polinomial. Por ejemplo, el problema de encontrar la mejor ruta para viajar se puede transformar en un problema de definición de carga de materiales con un cierto valor en un contenedor de capacidad limitada, como lo es el problema Knapsack.
Al conocer estas clases de problemas y los tipos de problemas que representan, podemos tener una idea de las consecuencias que puede traer la resolución de este problema. Si alguien demuestra que P equivale a NP, probablemente se desarrollarían algoritmos para resolver rápidamente un problema complejo, como el mejor recorrido para visitar todas las capitales de Brasil. Al resolver este problema y saber las características de los problemas de NP-completo, también se resolverían otros numerosos problemas de extrema complejidad, como los problemas industriales clásicos, lo cual permitiría importantes descubrimientos, desde nuevos medicamentos para enfermedades como el cáncer a la predicción de estructuras de proteínas. También habría consecuencias serias, como la decodificación de sistemas de cifrado, ya que sus resoluciones se volverían sencillas.
Comprobar lo opuesto, que P es diferente de NP, también aportaría grandes beneficios: permitiría una mejor orientación en la investigación futura y una dirección en teoría de complejidad informática. Por ejemplo, se podría profundizar la investigación en métodos de heurística y metaheurística, los cuales pretenden encontrar buenas soluciones, pero no necesariamente garantizan optimización.
Por lo tanto, cualquier respuesta a este importante problema traería grandes repercusiones al mundo como lo conocemos. Si piensa que sabe la respuesta de si P = NP, no pierda el tiempo, ¡porque el club de los millonarios está esperando por usted!
Coautor: Fabio Silva - Gerente Senior en Cassotis Consulting