Imagine que es un ladrón robando una exhibición de Museo de joyas tentadoras, geodas y gemas raras. Eres nuevo en esto, así que sólo trajiste una sola mochila. Su objetivo debe ser conseguir lejos con los objetos más valiosos sin sobrecargar su bolsa hasta que se rompa o se vuelve demasiado pesada para llevar. ¿Cómo eliges entre los objetos para maximizar tu botín? Podría enumerar todos los artefactos y sus pesos para elaborar la respuesta a mano., Pero cuantos más objetos haya, más gravoso será este cálculo para una persona—o una computadora.
este dilema ficticio, el» problema de la mochila», pertenece a una clase de problemas matemáticos famosos por empujar los límites de la computación. Y el problema de la mochila es más que un experimento mental. «Muchos de los problemas que enfrentamos en la vida, ya sean Negocios, Finanzas, incluida la logística, la carga de buques portacontenedores, la carga de aviones, Todos son problemas de mochila», dice Carsten Murawski, profesor de la Universidad de Melbourne en Australia., «Desde una perspectiva práctica, el problema de las mochilas es omnipresente en la vida cotidiana.»
Los investigadores una vez aprovecharon la complejidad del problema para crear sistemas de seguridad informática, pero estos ahora se pueden descifrar ya que el problema ha sido tan bien estudiado. Hoy en día, mientras la tecnología capaz de romper las cerraduras de nuestras comunicaciones digitales se cierne en el horizonte, el problema de las mochilas puede inspirar nuevas formas de prepararse para esa revolución.
Todo O Nada
el problema de la mochila pertenece a una clase de problemas «NP», que significa «tiempo polinómico no determinista».,»El nombre hace referencia a cómo estos problemas obligan a una computadora a pasar por muchos pasos para llegar a una solución, y el número aumenta drásticamente en función del tamaño de las entradas, por ejemplo, el inventario de artículos para elegir cuando se rellena una mochila en particular. Por definición, los problemas de NP también tienen soluciones que son fáciles de verificar (sería trivial verificar que una lista particular de elementos, de hecho, quepa en una mochila).,
«El problema que los teóricos comenzaron a examinar fue la eficiencia con que una tarea particular puede llevarse a cabo en una computadora», escribe Keith Devlin en el libro The Millennium Problems. Por ejemplo: dada una lista de 1 millón de artefactos de Museo con sus pesos y valores monetarios, y una mochila limitada a 25 libras, una computadora tendría que analizar todas las combinaciones posibles para generar la única con el botín más lucrativo. Dada una cantidad indefinida de tiempo, una computadora podría usar la fuerza bruta para optimizar casos grandes como este, pero no en escalas de tiempo que serían prácticas.,
«creemos que podría cubrir toda la tierra con procesadores y ejecutarlos hasta la muerte por calor del universo y aún así no resolver casos relativamente pequeños de versiones apropiadas de estos problemas», dice Noah Stephens-Davidowitz, investigador de Microsoft en el Instituto Simons en Berkeley, California.
algunos problemas de NP como el ejemplo de la mochila tienen una propiedad especial: a principios de la década de 1970, Stephen Cook y Richard Karp mostraron que una variedad de problemas de NP podrían convertirse en un solo problema de lógica formal., Por lo tanto, si uno pudiera ser resuelto y verificado eficientemente con un algoritmo, todos podrían. Esta propiedad se conoce como » integridad NP.»
una de las preguntas más difíciles en Ciencias de la computación y Matemáticas es si estos problemas «NP», incluyendo el problema de la mochila, son realmente diferentes de los problemas» P», aquellos que se pueden resolver en lo que se llama tiempo polinómico. Si P=NP, entonces es posible resolver todos los problemas cuyas soluciones son fáciles de verificar, dice Stephens-Davidowitz. Por lo tanto, si esta desigualdad persiste, el problema general de las mochilas siempre será difícil.,
mantener las cosas en secreto
a los investigadores de criptografía les encantan los problemas que son difíciles de resolver para las computadoras porque son útiles para cifrar mensajes digitales. Los códigos de seguridad Tipo Mochila no son útiles para esto, ya que son demasiado fáciles de descifrar, pero se están desarrollando métodos más complicados inspirados por este problema, y un día pueden jugar un papel en burlar a la próxima generación de computación.,
en un método de cifrado de estilo mochila temprano, la Clave Privada de una persona sería una lista de números en la que cada uno es más grande que la suma de sus predecesores. Los intercambios que involucran a esa persona usarían una Clave Pública que parece aleatoria pero está compuesta por números de la primera lista con transformaciones específicas aplicadas. Por ejemplo, si la clave pública es , el mensaje transmitido «1, 0, 0, 1» sería codificada como 2+0+0+5 = 7 (porque 2*1=2, 3*0=0, 4*0=0, y 5*1=5). Los números secretos involucrados en las conversiones entre claves permiten revelar el mensaje original.,
para que esto funcione, una computadora también debe averiguar si un número dado puede escribirse como la suma de un subconjunto de números en la Clave Privada, lo que se convierte en un problema fácil. Es similar a llenar una mochila con un lote de artículos de tamaño diferente, como un anillo, una pintura, un automóvil y una casa, y saber que no puedes meter nada más después de verificar que el anillo y la pintura encajen. Los criptógrafos Ralph Merkle y Martin Hellman describieron esta idea en 1978, pero otros descubrieron cómo descifrarla a principios de la década de 1980.,
Los intercambios privados de información en Internet de hoy a menudo usan claves que involucran números primos grandes, y aunque factorizar números grandes es difícil, no se cree que pertenezca a la misma clase «NP completo» que el problema de la mochila. Sin embargo, los científicos de la computación ya se están preparando para un futuro en el que las computadoras cuánticas puedan desbloquear rápidamente estas llaves.
Las computadoras cuánticas se basan en los principios de la mecánica cuántica, que dice que una partícula no se encuentra en una sola posición, sino que tiene una probabilidad de estar en muchos lugares diferentes a menos que se fije y se mida., Mientras que las computadoras normales codifican información en 0s y 1s, cada «qubit» en una computadora cuántica tendría una amplia gama de estados posibles relacionados con las propiedades de las partículas. Las computadoras cuánticas no serían útiles para navegar por internet o escribir un guion en una cafetería, pero desatarían un poder nunca antes visto en algunos tipos de problemas matemáticos. Desafortunadamente, esos problemas matemáticos constituyen los cimientos de la ciberseguridad moderna.
«en cierto sentido, tuvimos muy mala suerte», dice Stephens-Davidowitz., «Logramos que la seguridad de internet descansara en la dureza de algunos de los pocos problemas que parecen ser difíciles para las computadoras clásicas pero fáciles para las computadoras cuánticas.»
mientras que la computación cuántica está en su infancia, algunos investigadores dicen que estamos atrasados en la preparación para ella. En 2016, el Instituto Nacional de estándares y Tecnología (NIST) pidió nuevos métodos de cifrado resistentes a los cuánticos, anunciando 26 semifinalistas el año pasado. Uno de estos tipos de algoritmo que se está desarrollando se llama Criptografía basada en red., En lugar de usar números, utiliza claves que existen en múltiples dimensiones e implican la formación de una estructura de celosía hecha de puntos equidistantes en el espacio. La pregunta es dónde están esos puntos, y qué tan cerca está un punto aleatorio dado a las coordenadas de una red. En esencia, se trata de un problema de mochila en más de una dimensión.
«mi obsesión actual es tratar de averiguar cuán seguras son estas cosas basadas en celosías, idealmente antes de usarlas para operar internet», dice Stephens-Davidowitz.,
«esto significa que necesitamos criptografía resistente cuántica mucho antes de lo que esperamos que la computadora cuántica alcance todo su potencial», dijo Leo Ducas, investigador del Centrum Wiskunde & Informatica en los Países Bajos.
Más allá de la investigación criptográfica, el problema de la mochila y sus primos completos NP están en todas partes en la vida real. Por ejemplo, es posible que haya oído hablar del problema del «vendedor ambulante», que también es NP completo., El desafío aquí es encontrar la ruta más corta para que un vendedor viaje entre un número determinado de ciudades antes de regresar al punto de partida. Estrechamente relacionado está el problema de enrutamiento de vehículos, que considera múltiples vehículos haciendo entregas.
Luciana Buriol, Profesora Asociada de la Universidade Federal do Rio Grande do Sul en Brasil, ha atacado este problema para tratar de encontrar nuevos enfoques para el sector de la salud., Trabajó con un servicio de atención domiciliaria donde médicos y enfermeras visitan a los pacientes en sus hogares y ayudaron a optimizar sus rutas, dado un número limitado de automóviles disponibles para el transporte.
«dados 300 pacientes y 15 cars, no se puede encontrar la solución en un tiempo razonable», dijo. «Si tienes días para ejecutar el algoritmo, lo encontrarás — pero tienes que encontrarlo en menos de 2 horas, de lo contrario nunca lo usarás en la práctica.»
ningún algoritmo único puede resolver estos problemas., En su lugar, Buriol encuentra formas rápidas de llegar a aproximaciones útiles para que puedan ponerse en acción.
Mochilas a nuestro alrededor
para aquellos de nosotros que no somos científicos de la computación y nos enfrentamos a este tipo de problemas en la vida real, ¿qué tan buenos somos? El grupo de Murawski encuentra resultados preliminares que cuando le das a los humanos problemas similares a las mochilas, también luchamos poderosamente., En pequeños experimentos en los que se les pidió a los participantes que llenaran una mochila en una pantalla de computadora con artículos que llevaban valores y pesos establecidos, las personas tendieron a tener más dificultades para optimizar el contenido de la mochila a medida que aumentaba el número de opciones de artículos, el mismo problema que tienen las computadoras. Los investigadores dicen que este hallazgo puede estar relacionado con la» sobrecarga de opciones»: la forma en que nos congelamos cuando se nos dan demasiadas opciones, incluso en situaciones simples como comprar mermelada en una tienda de comestibles.
sin embargo, en el mundo real, nos las arreglamos. Prestar atención también es un problema de mochila., Al conducir, nos enfrentamos a una cornucopia de posibles distracciones como pájaros, nubes, la radio y edificios circundantes. Debemos poner solo los estímulos más pertinentes en nuestras mochilas mentales—y generalmente lo hacemos.
la pregunta sigue siendo: dado que los problemas completos de NP son más difíciles para las computadoras que otros tipos de enigmas, ¿también son más difíciles para las personas? Los limitados resultados iniciales sugieren que podrían ser, lo que sorprendió a Murawski.,
«si esto resulta ser el caso, sugeriría que la dureza de tales problemas es una característica de los problemas—una propiedad de la naturaleza—y no en el ojo del espectador», dice Murawski.