El investigador desarrolla una nueva herramienta para comprender problemas computacionales difíciles y aparentemente intratables

En algunos casos, el diámetro de cada pico será mucho menor que las distancias entre los diferentes picos. Por lo tanto, si uno tuviera que elegir dos puntos en este paisaje en expansión, es decir, dos posibles «soluciones», estarían muy cerca (si provienen del mismo pico) o muy separados (si provienen de diferentes picos) . En otras palabras, habrá una «brecha» reveladora en estas distancias, pequeña o grande, pero nada intermedio. Crédito: David Jamarnik et al.

La idea de que algunos problemas computacionales en matemáticas e informática pueden ser difíciles no debería ser una sorpresa. Hay, de hecho, toda una clase de problemas para los que se considera imposible resolver matemáticamente. Debajo de esta categoría se encuentran algunos problemas «más fáciles» que no se entienden bien, y que también pueden ser imposibles.


David Jamarnik, profesor de Investigación de Operaciones en la Escuela de Administración Sloan del MIT y el Instituto de Datos, Sistemas y Sociedad, enfoca su atención en la última categoría de problemas menos estudiados, que son más relevantes para el mundo cotidiano porque involucran Aleatorio—Una característica integral de los sistemas naturales. Él y sus colegas han desarrollado una poderosa herramienta para analizar estos problemas llamada propiedad de la brecha superpuesta (o OGP). Gamarnik describió la nueva metodología en un artículo de investigación reciente en procedimientos de la Academia Nacional de Ciencias.

PNP

Hace cincuenta años se formuló el problema más famoso de la informática teórica. P ≠ NP pregunta si hay problemas que involucran grandes conjuntos de datos cuya respuesta se puede verificar con relativa rapidez, pero que, incluso si se trabaja en las computadoras más rápidas disponibles, tomaría un tiempo absurdamente largo para resolver.

La conjetura P ≠ NP sigue sin probarse, pero la mayoría de los científicos informáticos creen que muchos problemas familiares, incluido, por ejemplo, el problema del viajante de comercio, entran en esta categoría increíblemente difícil. El desafío en el ejemplo del vendedor es encontrar la ruta más corta, en términos de distancia o tiempo, a través de N ciudades diferentes. La tarea se maneja fácilmente cuando N = 4, porque solo hay seis caminos posibles a considerar. Pero en 30 ciudades, hay más de 1030 formas posibles, y los números aumentan exponencialmente a partir de ahí. La mayor dificultad radica en diseñar un archivo algoritmo Resuelve el problema rápidamente en todos los casos, para todos los valores enteros de N. Los informáticos confían, basándose en la teoría de la complejidad computacional, en que no existe tal algoritmo, lo que confirma que P ≠ NP.

Hay muchos otros ejemplos de tales problemas intratables. Suponga, por ejemplo, que tiene una tabla de números enorme con miles de filas y miles de columnas. ¿Puedes encontrar, de todas las combinaciones posibles, la disposición exacta de diez filas y 10 columnas tal que sus cien entradas tengan la suma más alta posible? «Las llamamos tareas de optimización, porque siempre estás tratando de encontrar la mayor o la mejor: la mayor suma de números, la mejor ruta a través de las ciudades, etc.», dice Jamarnik.

Hace tiempo que los informáticos se dieron cuenta de que no se puede crear un algoritmo rápido que pueda, en todos los casos, resolver problemas de manera tan eficiente como la saga del viajante de comercio. «Es probable que tal cosa sea imposible por razones bien entendidas», señala Jamarnik. «Pero en la vida real, la naturaleza no genera problemas desde una perspectiva hostil. No trata de frustrarte con un problema finamente seleccionado y el más desafiante que se pueda concebir». De hecho, las personas suelen encontrar problemas en circunstancias más aleatorias y menos gestionadas, y estos son los problemas que la Alianza para el Gobierno Abierto pretende abordar.

Picos y valles

Para entender de qué se trata la Open Government Partnership, puede ser útil ver primero cómo se originó la idea. Desde la década de 1970, los físicos han estado estudiando el vidrio giratorio, materiales que tienen propiedades tanto de líquidos como de sólidos que tienen comportamientos magnéticos inusuales. La investigación de los vidrios giratorios ha dado lugar a una teoría general de sistemas complejos relacionados con problemas de física, matemáticas, informática, ciencia de los materiales y otros campos. (Este trabajo le valió a Giorgio Baresi el Premio Nobel de Física 2021).

Un problema confuso al que se han enfrentado los físicos es tratar de predecir el estado de energía, en particular las configuraciones de energía más bajas, de diferentes estructuras de vidrio giratorio. La situación a veces se representa en un «paisaje» de innumerables picos de montañas separados por valles, donde el objetivo es ubicar el pico más alto. En este caso, el pico más alto en realidad representa el estado de energía más bajo (aunque se podría voltear la imagen y buscar el agujero más profundo). Esto resulta ser un problema de optimización similar en forma al dilema del viajante de comercio, explica Jamarnik: «Tienes este enorme conjunto de montañas, y parece que la única manera de encontrar más alto es escalando cada una de ellas», una tarea absurda similar a encontrar una aguja en un pajar.

Los físicos han demostrado que se puede simplificar esta imagen y dar un paso hacia una solución cortando montañas a una cierta altura predeterminada e ignorando todo lo que esté por debajo de ese nivel de corte. Luego, dejará un grupo de picos prominentes sobre una capa uniforme de nubes, y cada punto de esos picos representará una posible solución al problema original.

En un artículo de investigación de 2014, Jamarnik y sus colegas notaron algo que anteriormente se había pasado por alto. Se dieron cuenta de que en algunos casos el diámetro de cada pico sería mucho más pequeño que las distancias entre los diferentes picos. Por lo tanto, si uno tuviera que elegir dos puntos en este paisaje en expansión, es decir, dos posibles «soluciones», estarían muy cerca (si provienen del mismo pico) o muy separados (si provienen de diferentes picos) . En otras palabras, habrá una «brecha» reveladora en estas distancias, pequeña o grande, pero nada intermedio. Jamarnik y sus colegas sugirieron que el sistema en este caso se caracteriza por OGP.

«Descubrimos que todos los problemas conocidos de naturaleza aleatoria computacionalmente difícil tienen una versión de esta propiedad», es decir, el diámetro de la montaña en el modelo esquemático es mucho más pequeño que la distancia entre las montañas, afirma Jamarnik. «Esto proporciona una medida más precisa de la solidez del algoritmo».

Desbloqueando los secretos de la complejidad de los algoritmos

La llegada de OGP podría ayudar a los investigadores a evaluar la dificultad de crear algoritmos rápidos para abordar problemas específicos. Ya les ha permitido «matemáticamente [and] Descartó enérgicamente una gran clase de algoritmos como competidores potenciales», dice Jamarnik. Hemos aprendido, específicamente, que los algoritmos estables, aquellos cuya salida no cambiará mucho si la entrada cambia solo un poco, no podrán resolver este tipo de problema de optimización. «Este resultado negativo se aplica no solo a las computadoras clásicas, sino también a las computadoras cuánticas y, específicamente, a los llamados «algoritmos de optimización de aproximación cuántica» (QAOA), que algunos investigadores esperaban que resolvieran los mismos problemas de optimización. Ahora, dados los resultados de Jamarnik y Según los hallazgos de los coautores, estas esperanzas se ven atenuadas por el reconocimiento de que se requerirán muchas capas de operaciones para que los algoritmos de tipo QAOA tengan éxito, lo que puede ser un desafío técnico.

«Si estas son buenas o malas noticias depende de tu punto de vista», dice. «Creo que es una buena noticia en el sentido de que nos ayuda a descubrir los secretos de la complejidad algorítmica y mejora nuestro conocimiento de lo que está en el ámbito de la probabilidad y lo que no. Es una mala noticia en el sentido de que nos dice que estos problemas son difíciles, aunque la naturaleza los produzca, y aunque se generen al azar». Agrega que la noticia no es realmente sorprendente. «Muchos de nosotros esperábamos esto todo el tiempo, pero ahora tenemos una base mucho más sólida para hacer esa afirmación».

Esto todavía deja a los investigadores a años luz de poder demostrar que no existen algoritmos rápidos que puedan resolver estos problemas de optimización en entornos aleatorios. Tener tal evidencia proporcionaría una respuesta definitiva al problema P NP. Él dice: «Si podemos demostrar que no podemos tener un algoritmo que funcione la mayor parte del tiempo, eso nos dice que definitivamente no podemos tener un algoritmo que funcione todo el tiempo».

Predecir cuánto tiempo pasará antes de que se resuelva el problema P NP parece ser un problema intratable en sí mismo. Es probable que haya muchos picos que escalar y valles que atravesar antes de que los investigadores obtengan una perspectiva más clara de la situación.


Resuelve «grandes problemas» con algoritmos mejorados con materiales 2D


más información:
David Jamarnik, La propiedad de brecha anidada: una barrera topológica para la optimización sobre estructuras estocásticas, procedimientos de la Academia Nacional de Ciencias (2021). DOI: 10.1073/pnas.2108492118

La frase: un investigador desarrolla una nueva herramienta para comprender problemas computacionales difíciles y aparentemente intratables (10 de enero de 2022), consultado el 10 de enero de 2022 en https://phys.org/news/2022-01-tool-hard-problems-intractable.html

Este documento está sujeto a derechos de autor. Sin perjuicio de cualquier trato justo con fines de estudio o investigación privados, ninguna parte puede reproducirse sin permiso por escrito. El contenido se proporciona únicamente con fines informativos.

READ  Lucha contra la viruela del simio durante el COVID-19

Deja una respuesta

Tu dirección de correo electrónico no será publicada.