La informática aparentemente sigue una curva de progreso imparable. Unas pocas décadas nos llevaron de los tubos de vacío a los microchips, del acceso telefónico a Internet de alta velocidad y al Office Assistant. clippy a ChatGPT. Sin embargo, miles de problemas cotidianos en la ciencia y la industria siguen siendo tan irresolubles como siempre para la flota actual de supercomputadoras impulsadas por IA.
Estos problemas notoriamente difíciles “NP-completos” prometen una premio millonariootorgado por la organización sin fines de lucro Clay Mathematics Institute, por encontrar su solución rápida o demostrar que no existe ninguna. Una sorprendente visión de la década de 1970 hace que este desafío sea aún más tentador: esos más de mil problemas son, en un sentido profundo, uno y el mismo. Si resuelves uno, los resuelves todos. Este concepto, ahora fundamental en el campo de la informática teórica, muestra que ciertos grupos de problemas computacionales forman una red unificada. Descubre un algoritmo rápido que resuelve Sudokus de cualquier tamaño, y ahora puedes romper los esquemas de cifrado que protegen nuestra economía digital. Revele un atajo para programar un recorrido aéreo dentro de un presupuesto y podrá usarlo para resolver casi cualquier problema abierto famoso. problema de matematicas.
Encontrar algoritmos rápidos para estos problemas NP-completos (o demostrar que no existen tales algoritmos) resolvería el problema “P versus NP”Pregunta, que es el misterio más importante de la informática. P se refiere al conjunto de problemas computacionales que las computadoras pueden resolver de manera eficiente. NP, por su parte, representa los problemas cuyas soluciones pueden ser verificado eficientemente. Pero esos problemas no necesariamente pueden resolverse rápidamente. NP incluye todo lo que hay en P (porque encontrar una solución es una manera perfectamente buena de verificarla) pero también problemas más difíciles para los cuales no conocemos métodos eficientes para resolverlos. descubrimiento soluciones. Sólo podremos verificarlos una vez que estén solucionados. La pregunta P versus NP pregunta si esta aparente asimetría entre encontrar una solución y verificarla es real o ilusoria. Quizás P = NP y se refieren al mismo conjunto de problemas. En otras palabras, tal vez los problemas NP que no sabemos resolver eficientemente sólo aparecer difícil en relación con los problemas P porque todavía tenemos que encontrar las ideas correctas.
Sobre el apoyo al periodismo científico
Si está disfrutando este artículo, considere apoyar nuestro periodismo galardonado al suscribiéndose. Al comprar una suscripción, ayudas a garantizar el futuro de historias impactantes sobre los descubrimientos y las ideas que dan forma a nuestro mundo actual.
Por ejemplo, ¿existe un algoritmo (una receta de instrucciones simples) que, dada una gran lista de ciudades, los vuelos que las conectan y un presupuesto, decidiría eficientemente si se pueden visitar todas respetando el presupuesto? No lo sabemos. conocemos un ineficiente Algoritmo: comprueba todas las secuencias posibles de vuelos que visitan todas las ciudades, suma el coste de cada uno y compara los totales con el presupuesto. Pero a medida que crece el número de ciudades en la lista, el número de rutas a revisar se dispara exponencialmente, convirtiéndose rápidamente en algo inviable incluso para las computadoras mas rapidas. Puede que exista o no algún atajo inteligente que eluda esta búsqueda exhaustiva, pero los científicos informáticos aún no lo han encontrado. dado un soluciónSin embargo, en este caso, una lista propuesta de vuelos, se podría verificar en un tiempo razonable si una ruta llega a todas las ciudades y se mantiene por debajo del presupuesto. Si P es igual a NP, implica que el escenario de vuelo (un ejemplo de lo que se llama el problema del vendedor ambulante) tiene una pronta solución. Simplemente no lo sabemos todavía.
Muchos problemas computacionales naturales se unen al problema del vendedor ambulante en el conjunto NP. Esto incluye desafíos de logística (como empacar cajas en camiones), redes sociales (encontrar camarillas de amigos en común), biología (predecir cómo se plegarán las proteínas), y juegos como Sudokus, Pokémon y caramelo aplastar. Incluso podemos considerar las matemáticas mismas como un problema NP porque sus demostraciones se pueden verificar de manera eficiente. Puede parecer extraño clasificarlos como problemas “difíciles” cuando la gente carga cajas en camiones y resuelve Sudokus todos los días. Pero consideramos que un algoritmo ha resuelto un problema de manera eficiente. solo si se resuelve cada ejemplo de manera eficiente, incluidos los muy grandes. Por supuesto, una computadora puede resolver un Sudoku de 9×9 más rápido que un millón x millón de Sudoku, por lo que la definición rigurosa de “eficiente” apela a cómo el tiempo requerido para resolver un problema aumenta con el tamaño de la entrada.
La pregunta P versus NP se refiere a una variedad de problemas computacionales y cómo se relacionan entre sí, por lo que puede parecer que una resolución requeriría investigar cada uno de esos problemas individualmente. Supongamos que descubre un algoritmo eficiente para el problema del agente ambulante. Esto sería un avance heroico, pero ¿te diría algo sobre tu capacidad para resolver enormes Sudokus o cualquier otro problema NP desafiante? Sorprendentemente, su algoritmo para ese único problema resolvería completamente P versus NP. En 1972, el científico informático Richard Karp publicó un papel fundamental demostrando que 21 problemas NP clásicos tienen una propiedad notable: un algoritmo eficiente para resolver cualquiera de ellos podría usarse no sólo para resolver los otros 20 sino también para resolver cada problema en NP. Llamó a estos 21 problemas NP-completos. En los años transcurridos, esa lista ha crecido a medida que los investigadores descubrieron que muchos otros problemas de NP comparten esta propiedad mágica (incluido el del vendedor ambulante).
Podemos ver la integridad NP con optimismo o pesimismo. Desde el punto de vista optimista, una fortaleza de problemas monstruosamente difíciles que se interpone entre nosotros y una promesa tecnológica incalculable ahora parece más bien un castillo de naipes. Si se tira a uno al ámbito de la viabilidad, todo el edificio de la NP se derrumba, y una revolución científica surge de entre los escombros, llena de viajes eficientes y sin esfuerzo, viajes rápidos. descubrimiento de fármacos mediante plegamiento de proteínas y una nueva era de las matemáticas. Por el lado pesimista, la completitud NP sugiere que estos problemas no tienen algoritmos eficientes; Si todo lo que se necesita para demostrar lo contrario equivale a resolver un solo problema, entonces ¿por qué nadie lo ha logrado todavía? La mayoría de los expertos inclinarse hacia esta última interpretación y sospechamos que los problemas NP-completos no tienen algoritmos rápidos.
Ya sea que se vea el vaso medio lleno o medio vacío, el concepto de problemas completos cambió la forma en que los investigadores ven la computación. Karp demostró que podía usar un algoritmo para un problema NP-completo para resolver otro demostrando primero que se pueden traducir problemas aparentemente no relacionados al lenguaje de cada uno mediante un proceso llamado reducción. Esto funciona mostrando cómo tomar cualquier instancia de un problema (como uno que involucra una lista de ciudades, vuelos entre ellas y un presupuesto) y convertirlo en otro problema (como un gran Sudoku) de tal manera que el Sudoku sólo tiene una solución válida si es posible visitar todas las ciudades dentro del presupuesto (y no tiene una solución válida en caso contrario). De esa manera, si descubriera un algoritmo eficiente para Sudoku, podría usarlo para resolver también el problema del vendedor ambulante al convertir instancias de este último en Sudoku. (Consulte la parte inferior de esta historia para ver un ejemplo interesante de reducción con todo detalle).
Esta capacidad de codificar un problema utilizando el lenguaje de otro no es sólo una peculiaridad de este ejemplo sino también una característica de la computación misma. Una red de reducciones une todos los problemas NP-completos. Resuelva cualquiera de ellos y podrá resolver cualquier otro problema NP. Las implicaciones aturden la mente. Recuerde que podemos enmarcar la demostración de teoremas matemáticos como un problema NP-completo. Elija cualquier pregunta matemática famosa sin resolver. La teoría de la completitud NP nos dice entonces que existe algún nivel de caramelo aplastar que codifica perfectamente tu pregunta de matemáticas. Si se puede lograr una determinada puntuación en una determinada cantidad de movimientos en ese nivel de Candy Crush, entonces su problema matemático tiene una prueba de cierta longitud; de lo contrario no es así. La completitud NP también nos asegura que ciertos avances en el plegamiento de proteínas (o el empaquetado de cajas o la resolución de Sudoku) destruirían la economía digital. Esto se debe a que el cifrado que protege nuestros datos confidenciales funciona protegiéndolos detrás de problemas computacionales que se consideran intratables. (Vale la pena señalar que, aunque resolver un problema NP-completo le permitiría romper el cifrado, lo contrario no es cierto; los problemas intratables que subyacen a la mayoría de los esquemas de cifrado no son del todo NP-completo en sí mismos).
Dado que todo esto depende de problemas NP completos, un millón de dólares podría parecer una ganga para su solución. Y podría ofrecerle un poco de motivación adicional la próxima vez que tenga dificultades para programar su viaje de vacaciones o resolver un Sudoku.
¿Cómo funciona la reducción?
Para cualquiera que quiera profundizar en cómo funciona la reducción, reduzcamos otro tipo de problema NP-completo, el “problema de tres colores del mapa”, al “problema de camarilla”. El problema de tres colores del mapa pregunta: Dado un mapa, ¿puedes asignar uno de tres colores a cada región para que ninguna región vecina repita un color? En cambio, el problema de la camarilla pregunta: Dada una red social, ¿contiene un grupo de un número deseado de personas que sean todas amigas en común? Ambos problemas son NP-completos, lo que significa que no conocemos ningún algoritmo eficiente para ninguno de ellos. En la superficie, tienen poco en común. Pero mostraremos que dado un mapa, podemos transformarlo en una red social de tal manera que la respuesta al problema de la red social nos dé la respuesta al problema del mapa.
Imagínese un mapa de EE. UU. Para construir una red social a partir de esto, designaremos tres “personas” para cada estado, una para cada uno de los tres colores: azul, verde y rojo. Luego haremos amigos de dos personas. a menos que:
-
Representan el mismo estado. (El representante verde de Wisconsin no será amigo del representante azul de Wisconsin).
-
Tienen el mismo color y representan a los estados vecinos. (Dakota del Norte y Dakota del Sur comparten una frontera, por lo que sus representantes rojos no serán amigos, pero Dakota del Norte y Florida no lo son, por lo que sus representantes rojos serán amigos).
Afirmo que esta red social de 150 personas contendrá un grupo de 50 amigos en común sólo si el mapa de Estados Unidos tiene una combinación válida de tres colores. Si encontramos 50 amigos mutuos en la red, todos deben representar estados diferentes porque, por diseño, no hicimos amigos a las personas cuando representaban el mismo estado. Además, el color que corresponde a la camarilla nunca asignaría el mismo color a los estados vecinos; prohibimos explícitamente tales vínculos en la red. Así, un grupo de 50 personas correspondería a una tricolor válida. Del mismo modo, si no existe ninguna camarilla de 50 en la red, entonces no existen tres colores para el mapa.
nosotros solo reducido del problema de los tres colores del mapa al problema de la camarilla. Esto significa que si alguien descubriera un algoritmo rápido para el problema de la camarilla, podría usarlo para resolver cualquier instancia del problema de los tres colores del mapa. Fundamentalmente, el primer paso (transformar el mapa en una red) es rápido. Crear las personas en la red y las relaciones de amistad adecuadas no requiere ninguna búsqueda exhaustiva ni otros gastos computacionales inviables. Las reducciones muestran que incluso si nuestros problemas parecen únicos, pueden ser más universales de lo que parecen.
Este es un artículo de opinión y análisis, y las opiniones expresadas por el autor o autores no son necesariamente las de Científico americano.