La noción de que algunos problemas computacionales en matemáticas e informática pueden ser difíciles no sorprender.De hecho, hay una clase completa de problemas que se consideran imposibles de resolver algorítmicamente.Justo debajo de esta clase se encuentran un poco de problemas "más fáciles" que son menos bien entendidos, y también pueden ser imposibles.
David Gamararnik, profesor de investigación de operaciones en la Escuela de Gestión MIT Sloan y el Instituto de Datos, Sistemas y Sociedad, está centrando su atención en esta última categoría de problemas menos estudio, que son más relevantes para el mundo cotidiano porque ellosimplica aleatoriedad: una característica integral de los sistemas naturales.Él y sus colegas han desarrollado una herramienta potente para analizar estos problemas llamados Propiedad de Gap de superposición (o OGP).Gamarnik describió la nueva metodología en un artículo reciente en las Actas de la Academia Nacional de Ciencias.
P ≠ NP
Hace cincuenta años, se formuló el problema más famoso en la informática teórica.Etiquetado como "P ≠ NP", pregunta si existen problemas que involucran vastas conjuntos de datos para los cuales se puede verificar una respuesta relativamente rápido, pero cuya solución, incluso si se resuelve en las computadoras disponibles más rápidas, tomaría un tiempo absurdamente largo..
La conjetura P ≠ NP aún no está probada, pero la mayoría de los científicos informáticos creen que muchos problemas familiares, incluido, por ejemplo, el problema del vendedor ambulante, caen en esta categoría imposiblemente difícil.El desafío en el ejemplo de vendedor es encontrar la ruta más corta, en términos de distancia o tiempo, a través de n diferentes ciudades.La tarea se gestiona fácilmente cuando n = 4, porque solo hay seis rutas posibles a considerar. But for 30 cities, there are more than 1030 possible routes, and the numbers rise dramatically from there.La mayor dificultad viene en el diseño de un algoritmo que resuelve rápidamente el problema en todos los casos, para todos los valores enteros de N.Los informáticos confían en la teoría de la complejidad algorítmica, que no existe tal algoritmo, afirmando así que P ≠ NP.
Hay muchos otros ejemplos de problemas intratables como este..Supongamos, por ejemplo, tiene una tabla gigante de números con miles de filas y miles de columnas.¿Puede encontrar, entre todas las combinaciones posibles, la disposición precisa de 10 filas y 10 columnas de modo que sus 100 entradas tendrán la suma más alta alcanzable?"Los llamamos tareas de optimización", dice Gamarnik, "porque siempre estás tratando de encontrar la mayor o mejor: la mayor suma de números, la mejor ruta a través de las ciudades, etc.."
Los informáticos han reconocido durante mucho tiempo que no puede crear un algoritmo rápido que pueda, en todos los casos, resolver problemas de manera eficiente como la saga del vendedor ambulante. “Such a thing is likely impossible for reasons that are well-understood," Gamarnik notes."Pero en la vida real, la naturaleza no genera problemas desde una perspectiva adversa.No está tratando de frustrarlo con el problema más desafiante y seleccionado a mano concebible." In fact, people normally encounter problems under more random, less contrived circumstances, and those are the problems the OGP is intended to address.
Picos y valles
Para comprender de qué se trata el OGP, primero podría ser instructivo ver cómo surgió la idea.Desde la década de 1970, los físicos han estado estudiando gafas de espín, materiales con propiedades de líquidos y sólidos que tienen comportamientos magnéticos inusuales.La investigación sobre gafas de espín ha dado lugar a una teoría general de sistemas complejos que es relevante para los problemas en física, matemáticas, informática, ciencias de los materiales y otros campos.(Este trabajo le valió a Giorgio Parisi un Premio Nobel de Física de 2021.)
Un problema con el que los físicos han luchado es tratar de predecir los estados de energía, y particularmente las configuraciones de energía más bajas, de diferentes estructuras de vidrio de espín.. The situation is sometimes depicted by a “landscape" of countless mountain peaks separated by valleys, where the goal is to identify the highest peak.En este caso, el pico más alto en realidad representa el estado de energía más bajo (aunque uno podría voltear la imagen y, en cambio, buscar el agujero más profundo). This turns out to be an optimization problem similar in form to the traveling salesman’s dilemma, Gamarnik explains: “You’ve got this huge collection of mountains, and the only way to find the highest appears to be by climbing up each one" — a Sisyphean chore comparable to finding a needle in a haystack.
Los físicos han demostrado que puede simplificar esta imagen y dar un paso hacia una solución, cortando las montañas a cierta elevación predeterminada e ignorando todo lo que está por debajo de ese nivel de corte.Luego se le dejaría una colección de picos que sobresalen por encima de una capa uniforme de nubes, con cada punto en esos picos que representan una solución potencial al problema original.
En un artículo de 2014, Gamarnik y sus coautores notaron algo que anteriormente se había pasado por alto.En algunos casos, se dieron cuenta, el diámetro de cada pico será mucho más pequeño que las distancias entre diferentes picos. Consequently, if one were to pick any two points on this sprawling landscape — any two possible “solutions" — they would either be very close (if they came from the same peak) or very far apart (if drawn from different peaks). In other words, there would be a telltale “gap" in these distances — either small or large, but nothing in-between.Un sistema en este estado, propuesto Gamarnik y colegas, se caracteriza por el OGP.
“We discovered that all known problems of a random nature that are algorithmically hard have a version of this property" — namely, that the mountain diameter in the schematic model is much smaller than the space between mountains, Gamarnik asserts.“Esto proporciona una medida más precisa de dureza algorítmica."
Desbloquear los secretos de la complejidad algorítmica
La aparición del OGP puede ayudar a los investigadores a evaluar la dificultad de crear algoritmos rápidos para abordar problemas particulares. And it has already enabled them “to mathematically [and] rigorously rule out a large class of algorithms as potential contenders," Gamarnik says."Hemos aprendido, específicamente, que los algoritmos estables, aquellos cuya salida no cambiará mucho si la entrada solo cambia un poco, fallará para resolver este tipo de problema de optimización." This negative result applies not only to conventional computers but also to quantum computers and, specifically, to so-called “quantum approximation optimization algorithms" (QAOAs), which some investigators had hoped could solve these same optimization problems.Ahora, debido a los hallazgos de Gamarnik y sus coautores, esas esperanzas han sido moderadas por el reconocimiento de que se requerirían muchas capas de operaciones para que los algoritmos de tipo QaoA tengan éxito, lo que podría ser técnicamente desafiante.
“Whether that’s good news or bad news depends on your perspective," he says."Creo que es una buena noticia en el sentido de que nos ayuda a desbloquear los secretos de la complejidad algorítmica y mejora nuestro conocimiento sobre lo que está en el ámbito de la posibilidad y lo que no es.Es una mala noticia en el sentido de que nos dice que estos problemas son difíciles, incluso si la naturaleza los produce, e incluso si se generan de manera aleatoria.." The news is not really surprising, he adds."Muchos de nosotros lo esperábamos todo el tiempo, pero ahora tenemos una base más sólida sobre la cual hacer esta afirmación."
Eso todavía deja a los investigadores a los años luz de poder demostrar la inexistencia de los algoritmos rápidos que podrían resolver estos problemas de optimización en entornos aleatorios.Tener una prueba de este tipo proporcionaría una respuesta definitiva al problema P ≠ NP. “If we could show that we can’t have an algorithm that works most of the time," he says, “that would tell us we certainly can’t have an algorithm that works all the time."
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 más picos para escalar, y valles para atravesar, antes de que los investigadores obtengan una perspectiva más clara de la situación..
