No es frecuente que los niños de 5 años puedan comprender preguntas en las fronteras de la informática, pero puede suceder. Supongamos, por ejemplo, que una niña de jardín de infantes llamada Alicia tiene dos manzanas, pero prefiere naranjas. Afortunadamente, sus compañeros de clase han desarrollado un saludable sistema de comercio de frutas con tipos de cambio estrictamente aplicados: renuncia a una manzana, por ejemplo, y podrás conseguir un plátano. ¿Puede Alice ejecutar una serie de intercambios, recogiendo y descargando plátanos o melones, que la lleven a su fruta favorita?

Suena bastante simple. “Puedes ir a la escuela primaria y contárselo a los niños”, dijo Christoph Haase, informático de la Universidad de Oxford. "La gente pensará: 'Eso debe ser fácil'".

Pero el problema matemático subyacente al dilema de Alice (llamado problema de accesibilidad para sistemas de suma de vectores) es sorprendentemente sutil. Si bien algunos casos pueden resolverse fácilmente, los informáticos lucharon durante casi medio siglo para desarrollar una comprensión integral del problema. Ahora, tras una serie de avances en los últimos años, han establecido firmemente cuán complejo puede llegar a ser ese problema.

Resulta que este problema infantil es absurdamente, casi caricaturescamente complejo, tan complejo que prácticamente todos los demás problemas computacionales famosos y difíciles Parece, bueno, un juego de niños. Intente cuantificar el esfuerzo necesario para resolver este problema y pronto se enfrentará a números tan grandes que incluso contar sus dígitos le hará alcanzar números de los que nunca ha oído hablar. Estas cifras a menudo invitan a realizar comparaciones con la escala del universo, pero incluso esas analogías se quedan cortas. “Eso no le haría justicia”, dijo Georg Zetzsche, científico informático del Instituto Max Planck de Sistemas de Software en Kaiserslautern, Alemania. "El universo es tan pequeño".

¿Al alcance?

Reducido a su esencia, el problema de la accesibilidad tiene que ver con objetos matemáticos llamados vectores, que son listas ordenadas de números. Las entradas de estas listas se denominan componentes y el número de componentes de un vector se denomina dimensionalidad. El inventario de frutas de Alice, por ejemplo, se puede describir mediante un vector de cuatro dimensiones (a, b, c, d), cuyos componentes representan cuántas manzanas, plátanos, melones y naranjas tiene en un momento dado.

Un sistema de suma de vectores, o VAS, es una colección de vectores que representan las posibles transiciones entre estados en un sistema. Para Alice, el vector de transición (−1, −1, 1, 0) representaría el intercambio de una manzana y un plátano por un melón. El problema de accesibilidad de VAS pregunta si existe alguna combinación de transiciones permitidas que puedan llevarle desde un estado inicial específico a un estado objetivo específico o, en términos matemáticos, si existe alguna suma de vectores de transición que transforme el vector inicial en el vector objetivo. Sólo hay un inconveniente: ningún componente del vector que describe el estado del sistema puede caer por debajo de cero.

"Esa es una restricción muy natural para un modelo de realidad", dijo Wojciech Czerwiński, informático de la Universidad de Varsovia. "No se puede tener un número negativo de manzanas".

En algunos sistemas, es fácil determinar si se puede alcanzar el vector objetivo. Pero ese no es siempre el caso. Los científicos informáticos están más interesados ​​en sistemas de suma de vectores de apariencia simple en los que no es obvio lo difícil que es determinar su accesibilidad. Para estudiar esos casos, los investigadores comienzan por definir un número que cuantifica el tamaño de un sistema determinado. Este número, representado por n, abarca el número de dimensiones, el número de transiciones y otros factores. Luego preguntan qué tan rápido puede aumentar la dificultad del problema de accesibilidad a medida que n se hace más grande.

Para responder a esa pregunta, los investigadores utilizan dos enfoques complementarios. Primero, buscan ejemplos de sistemas de suma de vectores particularmente complicados en los que determinar la accesibilidad requiere un nivel mínimo de esfuerzo. Esos niveles mínimos se denominan “límites inferiores” de la complejidad del problema; les dicen a los investigadores: “Los sistemas más complicados para una situación determinada n son al menos así de difíciles”.

En segundo lugar, los investigadores intentan establecer “límites superiores”: límites sobre cuán difícil puede llegar a ser la accesibilidad, incluso en los sistemas más diabólicos. Estos dicen: "Los casos más complicados para un determinado n son como mucho así de difíciles”. Para determinar con precisión qué tan difícil es la accesibilidad en los sistemas más complicados, los investigadores intentan empujar los límites inferiores hacia arriba y los límites superiores hacia abajo hasta que se encuentren.

La materia de las pesadillas

Los sistemas de suma de vectores tienen una larga historia. Desde la década de 1960, los informáticos los han utilizado para modelar programas que dividen un cálculo en muchas partes pequeñas y trabajan en esas partes simultáneamente. Este tipo de “computación concurrente” ahora es omnipresente, pero los investigadores aún no comprenden completamente sus fundamentos matemáticos.

En 1976, el informático ricardo lipton dio el primer paso hacia la comprensión de la complejidad del problema de accesibilidad de VAS. Desarrolló un procedimiento para construir sistemas en el que la forma más rápida de determinar si un estado es alcanzable desde otro es trazar una secuencia de transiciones entre ellos. Eso le permitió utilizar la longitud del camino más corto entre dos estados cuidadosamente elegidos como medida de la dificultad del problema de accesibilidad.

Lipton entonces demostrado podría construir un sistema de tamaño n en el que el camino más corto entre dos estados implicaba más de $latex 2^{2^n}$ transiciones. Eso implicaba un correspondiente límite inferior doble exponencial en el esfuerzo requerido para determinar la accesibilidad en sus sistemas. Fue un descubrimiento sorprendente: el crecimiento doble exponencial es el tema de las pesadillas de los científicos informáticos. De hecho, los investigadores a menudo se resisten incluso al crecimiento exponencial ordinario, que palidece en comparación: $látex {2^5}= 32$, pero $látex 2^{2^5}$ supera los 4 mil millones.

La mayoría de los investigadores pensaron que Lipton había ideado los sistemas de suma de vectores más complejos posibles, lo que significa que había elevado el límite inferior lo más alto posible. Lo único que faltaría, en ese caso, sería un límite superior que lo acompañara, es decir, una prueba de que no podría haber ningún sistema en el que determinar la accesibilidad fuera aún más difícil. Pero nadie sabía cómo demostrarlo. El informático Ernst Mayr estuvo más cerca cuando demostrado en 1981 que siempre es posible, en principio, determinar la accesibilidad en cualquier sistema de suma de vectores. Pero su prueba no puso ningún límite cuantitativo sobre cuán difícil podría ser el problema. Había suelo, pero no se veía ningún techo.

"Ciertamente pensé en ello de vez en cuando", dijo Lipton. “Pero después de un tiempo me di por vencido y, hasta donde yo sé, nadie hizo ningún progreso durante unos 40 años”.

En 2015, los informáticos Jérôme Leroux y Sylvain Schmitz finalmente establecido un límite superior cuantitativo – uno tan alto que los investigadores asumieron que era sólo un primer paso que podría empujarse hacia abajo para alcanzar el límite inferior de Lipton.

Pero eso no es lo que pasó. En 2019, los investigadores descubrieron un límite inferior mucho más alto que el de Lipton, poniendo fin a décadas de sabiduría convencional. El problema de la accesibilidad de los VAS era mucho más complejo de lo que nadie había previsto.

Una torre de poderes

El impactante resultado de 2019 surgió del fracaso. En 2018, Czerwiński refutó una conjetura de Leroux y Filip Mazowiecki, un científico informático que ahora trabaja en la Universidad de Varsovia, eso habría ayudado a avanzar en un problema relacionado. En discusiones posteriores, los investigadores dieron con una nueva y prometedora forma de construir sistemas de adición de vectores extracomplejos, lo que podría implicar un nuevo límite inferior en el problema de accesibilidad de los VAS, donde el progreso se había estancado durante tanto tiempo.

“En mi mente, todo estaba relacionado con la accesibilidad de VAS”, recordó Czerwiński. Durante un semestre con poca carga docente, decidió centrarse exclusivamente en ese problema, junto con Leroux, Mazowiecki y otros dos investigadores: Sławomir Lasota de la Universidad de Varsovia y Ranko Lazić de la Universidad de Warwick.

Después de unos meses, sus esfuerzos dieron sus frutos. Czerwiński y sus colegas demostrado que podían construir sistemas de suma de vectores en los que el camino más corto entre dos estados estuviera relacionado con el tamaño del sistema mediante una operación matemática llamada tetración que hace que incluso el doble crecimiento exponencial de pesadilla parezca manso.

La tetración es una extensión sencilla de un patrón que conecta las operaciones más familiares en matemáticas, comenzando con la suma. Añadirlos a la vez n copias de un número, y el resultado es equivalente a multiplicar ese número por n. Si multiplicas juntos n copias de un número, eso es equivalente a la exponenciación, o elevar el número al nº poder. La tetración, a menudo representada por un par de flechas que apuntan hacia arriba, es el siguiente paso en esta secuencia: Tetrar un número por n significa exponenciarlo n tiempos para producir una torre de poderes n pisos de altura.

Es difícil entender lo rápido que la tetración se sale de control: $latex 2 uparrowuparrow 3$, o $latex 2^{2^2}$, es 16, $latex 2 uparrowuparrow 4$ es un poco más de 65,000 2, y $latex 5 uparrowuparrow 20,000$ es un número con casi 2 dígitos. Es físicamente imposible escribir todos los dígitos de $latex 6 uparrowuparrow XNUMX$, una desventaja de vivir en un universo tan pequeño.

En su histórico resultado, Czerwiński y sus colegas demostraron que existen sistemas de suma de vectores de tamaño n donde la mejor manera de determinar la accesibilidad es trazar un camino que involucre más de $latex 2 uparrowuparrow n$ transiciones, lo que implica un nuevo límite inferior que eclipsó el de Lipton. Pero por muy confusa que sea la tetración, todavía no era la última palabra sobre la complejidad del problema.

Hasta Quinquagintillion y más allá 

Apenas unos meses después del impactante nuevo límite inferior de la complejidad de la accesibilidad de los VAS, Leroux y Schmitz empujado hacia abajo el límite superior que habían establecido tres años antes, pero no llegaron hasta la tetración. En cambio, demostraron que la complejidad del problema de accesibilidad no puede crecer más rápido que una monstruosidad matemática llamada función de Ackermann.

Para comprender esa función, llevemos el patrón utilizado para definir la tetración hasta su sombría conclusión. La siguiente operación de la secuencia, llamada pentación, representa la tetración repetida; le sigue otra operación (hexación) para pentación repetida, y así sucesivamente.

La función de Ackermann, denotada $látex A(n)$, es lo que obtienes cuando subes un escalón en esta escalera de operaciones con cada parada en la recta numérica: $látex A(1) = 1 + 1$, $látex A (2) = 2 × 2$, $látex A(3) = 3^3$, $látex A(4)=4 flecha arribaflecha arriba 4=4^{4^{4^4}}$, y así sucesivamente. El número de dígitos en $látex A(4)$ es en sí mismo un número colosal aproximadamente igual a 1 quincuagintillón; ese es el nombre caprichoso y rara vez necesario para un 1 seguido de 153 ceros. "No te preocupes por Ackermann de 5", aconsejó Javier Esparza, informático de la Universidad Técnica de Múnich.

El resultado de Leroux y Schmitz dejó una gran brecha entre los límites inferior y superior: la complejidad precisa del problema de accesibilidad del VAS podría encontrarse en cualquier extremo del rango o en cualquier punto intermedio. Czerwiński no tenía intención de dejar que esa brecha se mantuviera. "Seguimos trabajando en esto porque estaba claro que era lo más importante que habíamos hecho en nuestras vidas", dijo.

El último avance se produjo en 2021, mientras Czerwiński asesoraba a un estudiante de segundo año llamado Łukasz Orlikowski. Le asignó a Orlikowski una variante simple del problema para ponerse al día, y el trabajo de Orlikowski los ayudó a ambos a desarrollar una nueva técnica que también se aplicaba al problema general de accesibilidad. Eso les permitió elevar el límite inferior sustancialmente, hasta el límite superior de Ackermann de Leroux y Schmitz. Trabajando de forma independiente, Leroux obtuvo un resultado equivalente casi al mismo tiempo.

Finalmente, los investigadores habían determinado la verdadera complejidad del problema de la accesibilidad. El límite inferior de Czerwiński, Orlikowski y Leroux demostró que existe una secuencia de sistemas de suma de vectores progresivamente más grandes en los que el camino más corto entre dos estados crece en proporción a la función de Ackermann. El límite superior de Leroux y Schmitz demostró que el problema de la accesibilidad no puede ser más complejo que eso: poco consuelo para cualquiera que espere un procedimiento práctico infalible para resolverlo. Es un ejemplo sorprendente de cuán sutiles pueden ser los problemas computacionales aparentemente simples.

nunca terminado

Los investigadores han seguido estudiando el problema de la accesibilidad de los VAS después de determinar su complejidad exacta, ya que muchas variantes de la pregunta siguen sin respuesta. Los límites superior e inferior de Ackermann, por ejemplo, no distinguen entre las diferentes formas de aumentar n, como aumentar la dimensionalidad de los vectores o aumentar el número de transiciones permitidas.

Recientemente, Czerwiński y sus colegas han progresos realizados Separar estos efectos distintos mediante el estudio de qué tan rápido puede aumentar la complejidad en variantes de sistemas de suma de vectores con dimensionalidad fija. Pero aún queda mucho por hacer: incluso en tres dimensiones, donde los sistemas de suma de vectores son fáciles de visualizar, la complejidad exacta del problema de accesibilidad sigue siendo desconocida.

"En cierto modo, es vergonzoso para nosotros", dijo Mazowiecki.

Los investigadores esperan que una mejor comprensión de casos relativamente simples les ayude a desarrollar nuevas herramientas para estudiar otros modelos de computación que sean más elaborados que los sistemas de suma de vectores. Actualmente, no sabemos casi nada sobre estos modelos más elaborados.

"Veo esto como parte de una búsqueda fundamental para comprender la computabilidad", dijo Zetzsche.

¿Cuánto está realizando una serie de encuestas para servir mejor a nuestra audiencia. Toma nuestro encuesta a lectores de informática y entrarás para ganar gratis ¿Cuánto mercancía.