Cuando el Clay Mathematics Institute ofreció premios individuales de 1 millón de dólares a siete problemas matemáticos sin resolver, es posible que hayan infravalorado una entrada… por mucho. Si los matemáticos resolvieran, de la manera correcta, la cuestión de la informática “P versus NP”, el resultado podría valer más de un millón de dólares: estarían descifrando la mayoría de los sistemas de seguridad en línea, revolucionando la ciencia e incluso resolviendo mecánicamente el otro. seis de los llamados Problemas del Milenio, todos los cuales fueron elegidos en el año 2000. Es difícil exagerar lo que está en juego en torno al problema sin resolver más importante en Ciencias de la Computación.
P versus NP se refiere a la aparente asimetría entre hallazgo soluciones a problemas y verificando soluciones a los problemas. Por ejemplo, imagina que estás planeando una gira mundial para promocionar tu nuevo libro. Accede a Priceline y comienza a probar rutas, pero cada una de las que prueba arruina su presupuesto total de viaje. Desafortunadamente, a medida que crece el número de ciudades en su gira mundial, el número de rutas posibles para verificar se dispara exponencialmente, haciendo rápidamente inviable incluso para las computadoras buscar exhaustivamente en cada caso. Pero cuando usted se queja, su agente le responde con una solución de secuencia de vuelos. Puede verificar fácilmente si su ruta se mantiene dentro del presupuesto simplemente verificando que llegue a todas las ciudades y sumando las tarifas para compararlas con el límite del presupuesto. Note la asimetría aquí: encontrando una solución Es difícil, pero verificar una solución es fácil.
La pregunta P versus NP pregunta si esta asimetría es real o una ilusión. Si puedes verificar eficientemente una solución a un problema, ¿eso implica que también puedes verificar eficientemente una solución a un problema? encontrar ¿una solución? Quizás un atajo inteligente pueda evitar la búsqueda entre millones de rutas potenciales. Por ejemplo, si su agente quisiera que usted encontrara una secuencia de vuelos entre dos aeropuertos remotos específicos respetando el presupuesto, también podría abandonar el igualmente inmenso número de rutas posibles para verificar, pero de hecho, este problema contiene estructura suficiente para que los informáticos hayan desarrollado un procedimiento rápido (algoritmo) que evita la necesidad de una búsqueda exhaustiva.
Se podría pensar que esta asimetría es obvia: por supuesto, a veces sería más difícil encontrar una solución a un problema que verificarla. Pero los investigadores se han sorprendido antes al pensar que ese es el caso, sólo para descubrir en el último minuto que la solución es igual de fácil. Por lo tanto, cada intento en el que intentan resolver esta cuestión para cualquier escenario solo expone aún más cuán monumentalmente difícil es demostrar de una forma u otra. P versus NP también aparece en todas partes en el mundo computacional, mucho más allá de los detalles específicos de nuestro escenario de viaje, hasta el punto de que ha llegado a simbolizar un santo grial en nuestra comprensión de la computación.
En el subcampo de informática teórica Llamada teoría de la complejidad, los investigadores intentan determinar con qué facilidad las computadoras pueden resolver varios tipos de problemas. P representa la clase de problemas que pueden resolver eficientemente, como ordenar una columna de números en una hoja de cálculo o encontrar la ruta más corta entre dos direcciones en un mapa. NP representa la clase de problemas para los cuales las computadoras pueden verificar soluciones de manera eficiente. Nuestro problema de la gira del libro, llamado Problema del vendedor ambulante por académicos, vive en NP porque tenemos un procedimiento eficiente para verificar que la solución de nuestro agente funcionó.
Observe que NP en realidad contiene a P como subconjunto porque resolver un problema directamente es una forma de verificar su solución. Por ejemplo, ¿cómo verificarías que 27 x 89 = 2403? Usted mismo resolvería el problema de multiplicación y comprobaría que su respuesta coincide con la reclamada. Normalmente representamos la relación entre P y NP con un diagrama de Venn simple:
La región dentro de NP pero no dentro de P contiene problemas que no pueden resolverse con ningún algoritmo eficiente conocido. (Los informáticos teóricos utilizan una definición técnica de “eficiente” que puede ser debatida, pero sirve como un sustituto útil del concepto coloquial). Pero no sabemos si eso se debe a que tales algoritmos no existen o simplemente los tenemos. No reunió el ingenio para descubrirlos. Aquí hay otra forma de formular la pregunta P versus NP: ¿Son realmente distintas estas clases? ¿O el diagrama de Venn colapsa en un círculo? ¿Todos los problemas NP admiten algoritmos eficientes? Aquí hay algunos ejemplos de problemas en NP que actualmente no se sabe que estén en P:
- Dada una red social, ¿existe un grupo de un tamaño específico en el que todas las personas que lo integran son amigas entre sí?
- Dada una colección variada de cajas para enviar, ¿pueden caber todas en un número específico de camiones?
- Dado un sudoku (generalizado a norte X norte cuadrículas de rompecabezas), ¿tiene solución?
- Dado un mapa, ¿puede el Los países serán coloreados. con sólo tres colores de modo que no haya dos países vecinos del mismo color?
Pregúntese cómo verificaría las soluciones propuestas para algunos de los problemas anteriores y luego cómo encontraría una solución. Tenga en cuenta que aproximar una solución o resolver un caso pequeño (la mayoría de nosotros podemos resolver un problema de 9 x 9 sudokus) no es suficiente. Para calificar como solución de un problema, un algoritmo necesita encontrar una solución exacta en todos los casos, incluidos los muy grandes.
Cada uno de los problemas se puede resolver mediante búsqueda de fuerza bruta (por ejemplo, pruebe todos los colores posibles del mapa y compruebe si alguno de ellos funciona), pero el número de casos a intentar crece exponencialmente con el tamaño del problema. Esto significa que si llamamos al tamaño del problema norte (por ejemplo, el número de países en el mapa o el número de cajas para empacar en camiones), entonces el número de cajas a verificar se parece a 2norte. Los superordenadores más rápidos del mundo no tienen esperanzas contra el crecimiento exponencial. Incluso cuando norte es igual a 300, un tamaño de entrada pequeño según los estándares de datos modernos, 2300 excede el número de átomos en el universo observable. Después de presionar “ir” en dicho algoritmo, su computadora mostraría un molinete giratorio que lo sobreviviría a usted y a sus descendientes.
Miles de otros problemas pertenecen a nuestra lista. Desde la biología celular hasta la teoría de juegos, la cuestión P versus NP llega a rincones lejanos de la ciencia y la industria. Si P = NP (es decir, nuestro diagrama de Venn se disuelve en un solo círculo) y obtenemos algoritmos rápidos para estos problemas aparentemente difíciles, entonces toda la economía digital se volvería vulnerable al colapso. Esto se debe a que gran parte de la criptografía que protege cosas como su número de tarjeta de crédito y contraseñas funciona ocultando información privada detrás de problemas computacionalmente difíciles que sólo pueden ser fáciles de resolver si conoce la clave secreta. La seguridad en línea tal como la conocemos se basa en suposiciones matemáticas no comprobadas que se desmoronan si P = NP.
Sorprendentemente, incluso podemos considerar las matemáticas mismas como un problema NP porque podemos programar computadoras para verificar pruebas de manera eficiente. De hecho, legendario matemático Kurt Gödel Planteó por primera vez el problema P versus NP en una carta a su colega John von Neumann en 1956, y expresó (en terminología antigua) que P = NP “tendría consecuencias de la mayor importancia. Es decir, obviamente significaría que… el trabajo mental de un matemático relacionado con preguntas de sí o no podría ser completamente reemplazado por una máquina”.
Si usted es un matemático preocupado por su trabajo, tenga la seguridad de que la mayoría de los expertos creen que P no es igual a NP. Aparte de la intuición de que a veces las soluciones deberían ser más difíciles de encontrar que de verificar, miles de los problemas NP más difíciles que no se sabe que estén en P han permanecido sin resolver en campos dispares, brillando con incentivos de fama y fortuna, y sin embargo, ni una sola persona ha diseñado un algoritmo eficiente para uno solo de ellos.
Por supuesto, el presentimiento y la falta de contraejemplos no constituyen una prueba. Para demostrar que P es diferente de NP, de alguna manera hay que descartar todos los algoritmos potenciales para todos los problemas NP más difíciles, una tarea que parece fuera del alcance de las técnicas matemáticas actuales. De hecho, este campo ha salido adelante demostrando los llamados teoremas de barrera, que dicen que categorías enteras de tentadoras estrategias de prueba para resolver P frente a NP no pueden tener éxito. No sólo no hemos podido encontrar una prueba sino que tampoco tenemos idea de cómo podría ser una prueba final.