En el siglo IV, el matemático griego Pappus de Alejandría elogió a las abejas por su "previsión geométrica". La estructura hexagonal de su panal parecía la forma óptima de dividir el espacio bidimensional en celdas de igual área y perímetro mínimo, lo que permitía a los insectos reducir la cantidad de cera que necesitaban para producir y gastar menos tiempo y energía construyendo su colmena.

O eso supusieron Pappus y otros. Durante milenios, nadie pudo probar que los hexágonos eran óptimos, hasta que finalmente, en 1999, el matemático Thomas Hales demostró que ninguna otra forma podía hacerlo mejor. Hoy en día, los matemáticos aún no saben qué formas pueden teselar tres o más dimensiones con el área de superficie más pequeña posible.

Este problema de la "espuma" ha resultado tener una amplia gama de aplicaciones: para los físicos que estudian el comportamiento de las pompas de jabón (o espumas) y los químicos que analizan la estructura de los cristales, para los matemáticos que exploran los arreglos de empaquetamiento de esferas y para los estadísticos que desarrollan técnicas efectivas de procesamiento de datos. .

A mediados de la década de 2000, una formulación particular del problema de la espuma también llamó la atención de los informáticos teóricos, quienes descubrieron, para su sorpresa, que estaba profundamente conectado con un importante problema abierto en su campo. Pudieron usar esa conexión para encontrar una nueva forma de alta dimensión con un área de superficie mínima.

“Me encanta este ida y vuelta”, dijo Asaf Naor de la Universidad de Princeton. “Algunas matemáticas antiguas se vuelven relevantes para la informática; la informática paga y resuelve la cuestión de las matemáticas. Es muy agradable cuando esto sucede”.

Pero a esa forma, aunque óptima, le faltaba algo importante: una base geométrica. Debido a que su existencia había sido probada utilizando técnicas informáticas, su geometría real era difícil de entender. Eso es lo que Naor, junto con Oded Regev, científico informático del Instituto Courant de la Universidad de Nueva York, se propuso corregir en una prueba publicada en línea el mes pasado.

"Es un muy buen final para la historia", dijo Regev.

Espumas cúbicas

Los matemáticos han considerado otras versiones del problema de la espuma, incluido lo que sucede si solo se permite dividir el espacio de acuerdo con lo que se llama la red de enteros. En esa versión del problema, tomas una matriz cuadrada de puntos espaciados uniformemente (cada uno separado por 1 unidad) y conviertes cada uno de esos puntos en el centro de una forma. El problema de la espuma “cúbica” pregunta cuál será el área de superficie mínima cuando deba colocar mosaicos en el espacio de esta manera.

Los investigadores inicialmente estaban interesados ​​en imponer esta restricción para comprender las propiedades de los espacios topológicos llamados variedades. Pero la pregunta tomó vida propia, volviéndose relevante en el análisis de datos y otras aplicaciones.

También es geométricamente interesante, porque cambia lo que podría significar "óptimo". En dos dimensiones, por ejemplo, los hexágonos regulares ya no pueden formar mosaicos en el plano si solo pueden desplazarse cantidades enteras en las direcciones horizontal y vertical. (Tienes que moverlos en cantidades irracionales en una de las dos direcciones).

Los cuadrados pueden. Pero, ¿es eso lo mejor que se puede hacer? como el matemático jaigyoung choe descubierto en 1989, la respuesta es no. La forma óptima es, en cambio, un hexágono aplastado en una dirección y alargado en otra. (El perímetro de dicho hexágono es de aproximadamente 3.86 cuando su área es 1, superando el perímetro del cuadrado de 4).

Estas diferencias pueden parecer triviales, pero se vuelven mucho más grandes en dimensiones más altas.

Entre todas las formas de un volumen dado, la que minimiza el área superficial es la esfera. Como n, el número de dimensiones crece, el área de la superficie de la esfera aumenta en proporción a la raíz cuadrada de n.

Pero las esferas no pueden embaldosar un espacio sin dejar huecos. Por otro lado, un n-cubo dimensional de volumen 1 lata. El problema es que su área de superficie es 2n, creciendo en proporción directa a su dimensión. Un cubo de 10,000 1 dimensiones de volumen 20,000 tiene un área de superficie de 400 10,000, mucho más grande que XNUMX, el área de superficie aproximada de una esfera de XNUMX XNUMX dimensiones.

Y entonces, los investigadores se preguntaron si podrían encontrar un "cubo esférico", una forma que forma mosaicos. n-espacio dimensional, como un cubo, pero cuya superficie crece lentamente, como la de una esfera.

Parecía poco probable. "Si desea que su burbuja llene exactamente el espacio y esté centrada en esta cuadrícula cúbica, es difícil pensar en qué usaría excepto una burbuja cúbica", dijo Ryan O´Donnell, científico informático teórico de la Universidad Carnegie Mellon. "Realmente parece que el cubo debería ser el mejor".

Ahora sabemos que no lo es.

La dureza de los problemas difíciles

Durante décadas, el problema de la espuma cúbica estuvo relativamente inexplorado en dimensiones más altas. Los primeros investigadores que lograron avances en él no procedían del ámbito de la geometría sino de la informática teórica. Lo encontraron por casualidad, mientras buscaban una manera de probar una declaración central en su campo conocida como el conjetura de juegos únicos. "La conjetura de los juegos únicos", dijo Regev, "es lo que veo actualmente como la mayor pregunta abierta en la informática teórica".

Propuesto en 2002 por subhash khot, un estudiante de posgrado en ese momento, la conjetura postula que si un problema en particular, uno que implica asignar colores a los nodos de una red, no se puede resolver exactamente, entonces encontrar incluso una solución aproximada es muy difícil. De ser cierta, la conjetura permitiría a los investigadores comprender la complejidad de una gran variedad de otras tareas computacionales de una sola vez.

Los científicos informáticos a menudo clasifican las tareas en función de si se pueden resolver con un algoritmo eficiente o si, en cambio, son "NP-difíciles" (lo que significa que no se pueden resolver de manera eficiente a medida que crece el tamaño del problema, siempre y cuando se cree ampliamente). pero la conjetura no probada sobre la complejidad computacional es cierta). Por ejemplo, el problema del viajante de comercio, que solicita el camino más corto necesario para visitar todas las ciudades de una red una sola vez, es NP-difícil. También lo es determinar si un gráfico, una colección de vértices conectados por bordes, se puede etiquetar con un máximo de tres colores para que dos vértices conectados tengan colores diferentes.

Resulta que es NP-difícil encontrar incluso una solución aproximada para muchas de estas tareas. Digamos que desea etiquetar los vértices de un gráfico con diferentes colores de una manera que satisfaga alguna lista de restricciones. Si es NP-difícil satisfacer todas esas restricciones, ¿qué tal tratar de cumplir solo el 90%, el 75% o el 50%? Por debajo de cierto umbral, podría ser posible generar un algoritmo eficiente, pero por encima de ese umbral, el problema se vuelve NP-difícil.

Durante décadas, los científicos informáticos han trabajado para establecer umbrales para diferentes problemas de optimización de interés. Pero algunas preguntas eluden este tipo de descripción. Si bien un algoritmo puede garantizar el 80 % de la mejor solución, puede ser NP-difícil lograr el 95 % de la mejor solución, lo que deja sin resolver la cuestión de dónde exactamente, entre el 80 % y el 95 %, el problema desemboca en territorio NP-difícil.

La conjetura de los juegos únicos, o UGC, ofrece una forma de identificar inmediatamente la respuesta. Hace una declaración que al principio parece más limitada: que es NP-difícil diferenciar entre un gráfico para el que puede satisfacer casi todo un determinado conjunto de restricciones de color (digamos, más del 99%) y un gráfico para que apenas puedes satisfacer (digamos, menos del 1%).

Pero poco después de que se propusiera el UGC en 2002, los investigadores demostraron que si la conjetura es cierta, se puede calcular fácilmente el umbral de dureza para cualquier problema de satisfacción de restricciones. (Esto se debe a que el UGC también implica que un algoritmo conocido logra la mejor aproximación posible para todos estos problemas). “Era precisamente el eje de todos estos problemas de optimización”, dijo O'Donnell.

Y así, los científicos informáticos teóricos se propusieron probar el UGC, una tarea que finalmente llevó a algunos de ellos a descubrir cubos esféricos.

Haciendo los problemas difíciles más difíciles

En 2005, O'Donnell trabajaba en Microsoft Research. Él y dos colegas... uriel feige, ahora en el Instituto Weizmann de Ciencias, y chico kinder, ahora en la Universidad Hebrea de Jerusalén, se unieron para abordar el UGC.

Tenían una vaga idea de cómo querían proceder. Comenzarían con una pregunta sobre gráficos, una que es muy similar al UGC. El llamado problema de corte máximo ("max-cut") pregunta, cuando se le da un gráfico, cómo dividir sus vértices en dos conjuntos (o colores) para que el número de aristas que conectan esos conjuntos sea el mayor posible. (Puede pensar en el corte máximo como una pregunta sobre la mejor manera de colorear un gráfico con dos colores, de modo que la menor cantidad posible de bordes conecte vértices del mismo color).

Si el UGC es verdadero, implicaría que, dado un gráfico aleatorio, un algoritmo de aproximación eficiente solo puede acercarse al 87% del corte máximo verdadero de ese gráfico. Hacer algo mejor sería NP-difícil.

Feige, Kindler y O'Donnell, en cambio, querían ir en la dirección opuesta: esperaban demostrar que el corte máximo es difícil de aproximar y luego usar eso para probar el UGC. Su plan se basó en la fuerza de una técnica llamada repetición paralela, una estrategia inteligente que hace que los problemas difíciles sean más difíciles.

Digamos que sabe que es NP-difícil distinguir entre un problema que puede resolver y uno que puede resolver en su mayoría. La repetición paralela le permite aprovechar eso para mostrar un resultado de dureza mucho más fuerte: que también es NP-difícil distinguir entre un problema que puede resolver y uno que apenas puede resolver. "Este fenómeno profundo y no intuitivo... está en las entrañas de muchas ciencias de la computación hoy en día", dijo Naor.

Pero hay una trampa. La repetición en paralelo no siempre amplifica la dificultad de un problema tanto como los informáticos quieren. En particular, hay aspectos del problema del corte máximo que “crean un gran dolor de cabeza para la repetición en paralelo”, dijo Regev.

Feige, Kindler y O'Donnell se centraron en demostrar que la repetición en paralelo podía funcionar a pesar de los dolores de cabeza. “Esto es algo realmente complicado de analizar”, dijo dana moshkovitz, científico informático teórico de la Universidad de Texas, Austin. “Pero esto parecía tentadoramente cercano. Parecía que la repetición paralela [ayudaría a hacer] esta conexión entre el corte máximo y los juegos únicos”.

Como calentamiento, los investigadores intentaron comprender la repetición paralela para un caso simple de corte máximo, lo que Moshkovitz llamó "el corte máximo más estúpido". Considere un número impar de vértices conectados por aristas para formar un círculo o "ciclo impar". Desea etiquetar cada vértice con uno de dos colores para que ningún par de vértices adyacentes tenga el mismo color. En este caso, eso es imposible: un borde siempre conectará vértices del mismo color. Debe eliminar ese borde, "romper" el ciclo impar, para que su gráfico satisfaga la restricción del problema. En última instancia, desea minimizar la fracción total de bordes que necesita eliminar para colorear correctamente su gráfico.

La repetición paralela le permite considerar una versión de alta dimensión de este problema, una en la que debe romper todos los ciclos impares que aparecen. Feige, Kindler y O'Donnell necesitaban demostrar que a medida que aumenta el número de dimensiones, debe eliminar una fracción muy grande de bordes para romper todos los ciclos impares. Si eso fuera cierto, significaría que la repetición paralela podría amplificar efectivamente la dureza de este problema de "corte máximo estúpido".

Fue entonces cuando el equipo descubrió una curiosa coincidencia: había una forma geométrica de interpretar si la repetición en paralelo funcionaría de la manera que esperaban. El secreto estaba en la superficie de las espumas cúbicas.

De limones a limonada

Su problema, reescrito en el lenguaje de las espumas, se reducía a mostrar que los cubos esféricos no pueden existir, que es imposible dividir el espacio de alta dimensión a lo largo de la red de enteros en celdas con un área de superficie mucho menor que la del cubo. (Un área de superficie más grande corresponde a la necesidad de eliminar más bordes "malos" en el gráfico de ciclos impares, como esperaban mostrar los científicos informáticos).

“Pensamos, oh, qué extraño problema de geometría, pero eso probablemente sea cierto, ¿verdad?” dijo O´Donnell. “Realmente necesitábamos que esa fuera la verdadera respuesta”. Pero él, Feige y Kindler no pudieron probarlo. Así que en 2007, ellos publicado un documento describiendo cómo planearon usar este problema para ayudar a atacar el UGC.

Muy pronto, sus esperanzas se desvanecieron.

Corrió Raz, un científico informático teórico de Princeton que ya había probado varios resultados importantes sobre la repetición en paralelo, estaba intrigado por su artículo. Decidió analizar la repetición paralela para el problema de los ciclos impares, en parte debido a la conexión con la geometría que habían descubierto Feige, Kindler y O'Donnell.

Raz no comenzó con el problema de la espuma, sino que atacó de frente la versión informática de la pregunta. Demostró que puede salirse con la suya eliminando muchos menos bordes para romper todos los ciclos impares en un gráfico. En otras palabras, la repetición paralela no puede amplificar suficientemente la dureza de este problema de corte máximo. “Los parámetros que uno obtiene de la repetición paralela exactamente, exactamente no alcanzan a dar esto”, dijo Moshkovitz.

“Nuestro plan de usar la repetición paralela para mostrar la dificultad de los juegos únicos ni siquiera funcionó en el caso más simple”, dijo O'Donnell. “Esto rompió todo el plan”.

Aunque decepcionante, el resultado de Raz también insinuó la existencia de cubos esféricos: formas capaces de teselar n-espacio dimensional con un área de superficie que escala en proporción a la raíz cuadrada de n. “Pensamos, bueno, hagamos limonada con limones y tomemos este resultado técnico decepcionante sobre la repetición paralela y los gráficos discretos, y convirtámoslo en un resultado ordenado e interesante en geometría”, dijo O'Donnell.

Él y Kindler, en colaboración con los informáticos Anup Rao y Avi Wigderson, estudiaron detenidamente la prueba de Raz hasta que aprendieron sus técnicas lo suficientemente bien como para traducirlas al problema de la espuma. En 2008 demostraron que los cubos esféricos son de hecho posibles.

“Es una buena manera de razonar sobre el problema”, dijo marca braverman de princeton "Es hermoso."

Y planteó preguntas sobre el lado geométrico de la historia. Debido a que utilizaron el trabajo de Raz sobre la repetición paralela para construir su forma de mosaico, Kindler, O'Donnell, Rao y Wigderson terminaron con algo feo y parecido a Frankenstein. El azulejo estaba desordenado y lleno de hendiduras. En términos matemáticos, no era convexo. Si bien esto funcionó para sus propósitos, el cubo esférico carecía de las propiedades que prefieren los matemáticos: propiedades que hacen que una forma sea más concreta, más fácil de definir y estudiar, y más adecuada para aplicaciones potenciales.

“Hay algo muy insatisfactorio en su construcción”, dijo Regev. “Parece una ameba. No se parece a lo que esperarías, un buen cuerpo embaldosado”.

Eso es lo que él y Naor se propusieron encontrar.

Liberarse de la jaula

Desde el principio, Naor y Regev se dieron cuenta de que tendrían que empezar de cero. "En parte porque los cuerpos convexos son tan restrictivos, ninguna de las técnicas anteriores tenía posibilidades de funcionar", dijo dorminzer, científico informático teórico del Instituto Tecnológico de Massachusetts.

De hecho, era completamente plausible que la convexidad fuera demasiado restrictiva, que un cubo esférico convexo simplemente no existe.

Pero el mes pasado, Naor y Regev demostraron que se puede dividir n-espacio dimensional a lo largo de coordenadas enteras con una forma convexa cuya superficie es bastante cercana a la de la esfera. Y lo hicieron completamente geométricamente, devolviendo el problema a sus raíces matemáticas.

Primero tuvieron que sortear un gran obstáculo. El problema de la espuma cúbica requiere que cada mosaico esté centrado en coordenadas enteras. Pero en la red de enteros, hay distancias muy cortas entre algunos puntos, y esas distancias cortas causan problemas.

Considere un punto en la cuadrícula bidimensional. Se encuentra a 1 unidad de distancia de sus puntos más cercanos en las direcciones horizontal y vertical. Pero en la dirección diagonal, el punto más cercano está a $latex sqrt{2}$ unidades de distancia, una discrepancia que empeora en espacios más grandes. En el nEnrejado de enteros -dimensional, los puntos más cercanos todavía están a 1 unidad de distancia, pero esos puntos "diagonales" ahora están a $latex sqrt{n}$ unidades de distancia. En, digamos, 10,000 100 dimensiones, esto significa que el vecino "diagonal" más cercano a cualquier punto está a 10,000 unidades de distancia, aunque hay otros 1 XNUMX puntos (uno en cada dirección) que están a solo XNUMX unidad de distancia.

En otras redes, esos dos tipos de distancias crecen en proporción entre sí. Los matemáticos saben desde hace décadas cómo teselar dichas redes con formas convexas de área de superficie mínima.

Pero en la red de enteros, las distancias más cortas siempre estarán fijadas en 1. Esto interfiere en la construcción de un mosaico atractivo con un área de superficie óptima. “Ellos te pusieron en esta jaula”, dijo Regev. “Hacen que todo esté muy apretado a tu alrededor”.

Entonces, Naor y Regev consideraron una porción del total n-espacio dimensional. Eligieron cuidadosamente este subespacio para que aún fuera rico en puntos enteros, pero ninguno de esos puntos estaría demasiado cerca.

En otras palabras, el subespacio con el que terminaron era precisamente del tipo que los matemáticos ya sabían cómo teselar de manera óptima.

Pero esto era sólo la mitad del trabajo. Naor y Regev necesitaban dividir todo el espacio, no solo una parte. para obtener un ncubo esférico bidimensional, tenían que multiplicar su mosaico eficiente con un mosaico del espacio restante (similar a cómo podrías multiplicar un cuadrado bidimensional con un segmento de línea unidimensional para obtener un cubo tridimensional). Hacerlo elevaría su construcción de regreso al espacio original, pero también aumentaría su área de superficie.

La pareja tuvo que demostrar que el azulejo del espacio restante, que no era tan óptimo, no agregaba demasiado a la superficie. Una vez que hicieron eso, su construcción estaba completa. (El área de superficie de su forma final terminó siendo un poco más grande que la del cubo esférico no convexo, pero creen que podría ser posible encontrar un mosaico convexo que sea tan eficiente como su contraparte no convexa).

“Su prueba es completamente diferente” del trabajo anterior sobre cubos esféricos, dijo el matemático. Noga Alon. “Y en retrospectiva, tal vez sea una prueba más natural. Esto es lo que alguien debería haber intentado para empezar”.

“Cuando las cosas se hacen de manera diferente”, agregó Raz, “a veces encuentras implicaciones adicionales interesantes”.

esperanza reavivada

Todavía no está claro cuáles podrían ser esas implicaciones, aunque el trabajo aprovecha el uso potencial de redes de enteros en criptografía y otras aplicaciones. Dado lo conectado que está este problema con otros campos, "es probable que conduzca a otras cosas", dijo Alon.

Por el momento, los informáticos no ven una forma de interpretar el resultado convexo en el lenguaje de repetición paralela y el UGC. Pero no han renunciado por completo al plan original de usar el problema de la espuma para probar la conjetura. “Hay varias formas de intentar subvertir las barreras obvias que encontramos”, dijo Kindler.

Braverman y Minzer probaron una de esas formas cuando espumas revisadas en 2020. En lugar de requerir que la forma del mosaico sea convexa, pidieron que obedezca ciertas simetrías, de modo que se vea igual sin importar cómo cambie sus coordenadas. (En 2D, un cuadrado funcionaría, pero un rectángulo no; tampoco lo harían los cubos esféricos de alta dimensión descritos hasta la fecha). Bajo esta nueva restricción, la pareja pudo mostrar lo que Kindler y otros esperaban hacer 15 años antes: que no puedes hacer mucho mejor que el área de la superficie del cubo después de todo.

Esto correspondía a un tipo diferente de repetición paralela, una que haría que el caso más simple de corte máximo fuera tan difícil como tenía que ser. Si bien el resultado ofrece alguna esperanza para esta línea de investigación, no está claro si esta versión de repetición paralela funcionará para todos los problemas de corte máximo. “Eso no significa que hayas terminado”, dijo Braverman. “Simplemente significa que estás de vuelta en el negocio”.

“Hay mucho potencial en la geometría”, dijo Minzer. “Es solo que no lo entendemos lo suficientemente bien”.