Los informáticos se acercan cada vez más a un importante objetivo algorítmico | Revista Cuanta

Si alguien le pide que determine si dos objetos son iguales, puede parecer una solicitud trivial. En la mayoría de los casos cotidianos, una mirada rápida es suficiente para emitir un juicio preciso.

Pero en informática, es una cuestión mucho más compleja. De hecho, es uno que llega al corazón no resuelto de lo que las computadoras son capaces de hacer. Dependiendo de cuáles sean los objetos y de cómo se defina la igualdad, todavía no sabemos si las computadoras pueden responder la pregunta rápidamente o si un enfoque lento y laborioso es esencialmente lo mejor que pueden manejar.

Durante la última década, ha habido algunos resultados importantes que demuestran que las computadoras pueden hacerlo al menos un poco mejor que eso. Uno de los mayores resultados recientes en informática fue un algoritmo más rápido para determinar cuándo dos gráficos son iguales. El trabajo de 2015, de László Babai de la Universidad de Chicago, rompió una importante barrera de velocidad computacional pero no alcanzó otra.

Ahora, un artículo de Xiaorui sol de la Universidad de Illinois, Chicago, ha presentado un algoritmo nuevo y más rápido para una pregunta relacionada llamada problema de isomorfismo de grupos, que consiste en saber cuándo dos objetos matemáticos llamados grupos son iguales. El trabajo, publicado en línea. este pasado mes de marzo, da un pequeño paso hacia la clarificación de la complejidad computacional subyacente involucrada en la comparación de objetos.

El trabajo de Sun rompe un límite de velocidad de larga data para una clase particular de grupos, el que se considera el caso más difícil de resolver del problema del isomorfismo de grupo. Si un algoritmo puede comparar rápidamente grupos de este tipo, la esperanza es que pueda comparar rápidamente grupos de cualquier tipo.

"No conocemos tal teorema, pero tenemos razones para creer que algo así debería ser cierto", dijo Josh Grochow de la Universidad de Colorado, Boulder.

comparando comparaciones

Para determinar si dos cosas son iguales de manera precisa, primero debe definir "lo mismo". Dos cadenas de números podrían considerarse iguales si simplemente contienen los mismos dígitos, o es posible que deban tener los mismos dígitos en el mismo orden.

El isomorfismo es un tipo particular de igualdad que surge mucho en matemáticas. Cuando dos objetos son isomorfos entre sí, significa aproximadamente que contienen los mismos elementos y que esos elementos están en la misma relación entre sí.

Los gráficos, colecciones de vértices (puntos) unidos por bordes (líneas), proporcionan una forma visual accesible de ver cómo puede verse el isomorfismo. Dos gráficos son isomorfos si puedes hacer coincidir los vértices de un gráfico con los vértices del otro, de modo que los vértices que están conectados por una arista en el primer gráfico están conectados por una arista en el segundo. Los gráficos isomorfos pueden verse diferentes en la superficie, pero comparten una estructura subyacente.

Los grupos son más abstractos que los gráficos, pero aún se pueden comparar por isomorfismo. Un grupo es una colección de elementos, como números, que se pueden combinar entre sí según alguna operación para que el resultado también esté en la colección. Por ejemplo, puede tener un grupo cuyos elementos sean los números enteros (todos los números enteros positivos y negativos, más cero) y cuya operación sea la suma: sume dos números enteros y el resultado siempre será otro número entero.

Dos grupos son isomorfos si puede emparejar cada elemento de un grupo con un elemento del otro, de modo que el resultado de operar con dos elementos del primer grupo sea coherente con el resultado de operar con los valores equivalentes de esos elementos del segundo. grupo.

Aquí hay un ejemplo simple de dos grupos, cada uno con dos elementos, que son isomorfos entre sí. El primer grupo consta de los números 0 y 1, y el segundo grupo consta de las letras a y b. Ambos grupos contienen una operación para combinar los elementos del grupo de una manera específica, con los resultados expuestos en las tablas a continuación.

Los grupos son isomorfos porque 0 se empareja con a, 1 pares con b, y la relación estructural que se produce al combinar elementos es la misma en ambos grupos.

“Decimos que dos grupos son isomorfos si son básicamente equivalentes”, dijo Sun.

Progreso desequilibrado

El isomorfismo es un concepto importante en matemáticas, donde los gráficos y los grupos se presentan ampliamente, porque permite a los matemáticos mirar más allá de las diferencias superficiales y enfocarse en las formas en que los objetos relacionados pueden ser realmente iguales. Pero también es fundamental en informática; Los investigadores no solo buscan algoritmos que determinen si dos objetos son isomorfos, sino que también miden qué tan rápido pueden ejecutarse esos algoritmos.

Esa medida puede ser complicada. La velocidad de un algoritmo se basa en cómo cambia su tiempo de ejecución con el tamaño de los objetos en los que está trabajando. Imagina, por ejemplo, que tienes dos pares de grupos. En un par, cada grupo contiene cinco elementos. En el otro, cada grupo contiene 10 elementos.

Es de esperar que un algoritmo tarde más tiempo en determinar si los grupos con más elementos son isomorfos. ¿Pero cuánto tiempo más? ¿Tomará el doble de tiempo? 5² ¿más extenso? 2⁵ ¿más extenso? Esas preguntas corresponden a importantes clasificaciones amplias de velocidad algorítmica: pueden ejecutarse en tiempo lineal (lo que significa que en este caso toma el doble de tiempo), tiempo polinomial (5² más largo) y el tiempo exponencial (2⁵ más).

Los informáticos saben en qué categoría de velocidad caen la mayoría de las preguntas informáticas, pero no todas.

“La mayoría son las más fáciles o las más difíciles [tipo de pregunta], pero todavía hay varias excepciones que se desconocen”, dijo Sun. El isomorfismo de grafos y grupos se encuentran entre esas excepciones, que es lo que los hace tan atractivos para estudiar.

En los 1970s, Roberto Tarjan de la Universidad de Princeton se dio cuenta de que existe un algoritmo que puede determinar si dos grupos cualesquiera son isomorfos con un tiempo de ejecución de $latex n^{{(log,n)}}$, donde n es el número de elementos en cada grupo. Esto se denomina algoritmo de tiempo cuasi-polinomial, y en la jerarquía de los tiempos de ejecución es mejor que el tiempo exponencial (2ⁿ) pero peor que el tiempo polinomial (n²). Esta es aproximadamente la misma velocidad que el algoritmo de isomorfismo gráfico de Babai, y sigue siendo lo mejor que podemos hacer para los grupos casi 50 años después.

“Más o menos significa que no ha habido progreso durante medio siglo”, dijo Sun.

En el momento del resultado de Tarjan, el problema del isomorfismo de grupos se estudiaba más ampliamente que la versión gráfica. Eso ha cambiado hoy, en parte porque el isomorfismo de grafos ha estimulado innovaciones interesantes, mientras que el isomorfismo de grupos se ha estancado.

“Todas nuestras herramientas han sido muy lentas durante años y ha sido difícil explotar lo que sabemos sobre el álgebra [de grupos]”, dijo James Wilson de la Universidad Estatal de Colorado.

Pero a pesar de esta disparidad en el progreso, los dos problemas tienen una conexión más profunda que la similitud de sus nombres: el problema de isomorfismo de grupo (al menos en esta formulación) se reduce al problema de isomorfismo de grafos. Esto significa que cualquier algoritmo que pueda resolver el problema del gráfico también puede resolver el problema del grupo en una cantidad de tiempo similar. Lo contrario no es cierto: el progreso en el grupo no implica el progreso en el gráfico. Pero la falta de avances en el problema de grupos ha pesado sobre los matemáticos que buscan avances proporcionales en el problema de grafos. ¿Cómo puedes lograr algo más difícil si primero no puedes lograr algo que está estrechamente relacionado y parece aún más fácil?

"En otras palabras", dijo Sun, "para mejorar aún más el isomorfismo de gráficos, el isomorfismo de grupo es un gran cuello de botella".

Un problema transformado

Cuando el progreso en un problema se estanca tanto como sucedió con el isomorfismo de grupo, por lo general es necesaria la invención para salir del estancamiento. “Cuando tienes un gran avance, eso debería ser una indicación de que hay una nueva idea”, dijo Grochow.

El trabajo de Sun contiene algunas ideas que implican apuntar a un tipo importante de grupo y encontrar una forma inteligente de dividir esos grupos en partes para poder compararlos.

Los grupos para los que trabaja el algoritmo de Sun se denominan p-grupos de clase 2 y exponente p. Son similares a los grupos en los que el producto de dos elementos es otro elemento y el producto sigue siendo el mismo independientemente del orden en que los multipliques. Pero lo que realmente importa es lo que representan para el problema general de isomorfismo de grupo. Estos grupos tienen una estructura muy simple, lo que significa que deberían ser fáciles de comparar. Pero a pesar de esta simplicidad, los investigadores no habían descubierto una forma de acelerar el algoritmo. Hasta que pudieran, parecía inútil hacer mejoras para la cuestión general del isomorfismo de grupo.

Sun comenzó cambiando la configuración de grupos a matrices, conjuntos de números que sirven como objetos fundamentales en el álgebra lineal. Esto fue posible gracias a un teorema de la década de 1930 llamado correspondencia de Baer, ​​que transforma esta versión de la cuestión del isomorfismo de grupos en un problema perfectamente análogo sobre matrices. En particular, Sun trabajó con espacios de matrices, que son colecciones de matrices con una propiedad especial: la combinación (lineal) de dos matrices en el espacio es igual a otra matriz en el espacio.

En otras palabras, estos espacios se estructuran mucho como grupos. Entonces, en lugar de tratar de entender cuándo dos grupos son isomorfos, Sun podría simplemente tratar de entender cuándo dos espacios de matriz son isométricos, una noción de isomorfismo de espacios de matriz que corresponde a la de grupos.

Sun no fue el primer investigador en adoptar este enfoque, pero fue el primero en introducir un paso adicional: dividir un espacio de matriz en dos partes. Una pieza es el núcleo del espacio, en el que todas las matrices son simples. La otra pieza es el espacio que rodea a ese núcleo, en el que todas las matrices son particularmente complejas. Este movimiento corresponde a dividir un grupo en subgrupos que contienen solo algunos de los elementos totales.

Luego, Sun aplicó diferentes métodos algorítmicos a cada una de estas piezas. El núcleo tiene una estructura simple, por lo que utilizó una caracterización de la estructura para representarla de una manera más organizada. La capa externa es más compleja, por lo que obviamente no hay una forma rápida de compararla con otra. En cambio, el método de Sun adopta un enfoque llamado individualización y refinamiento para descartar la mayoría de las formas posibles de mapear una capa externa sobre la otra y luego usa una computadora para trabajar con todas las formas posibles restantes para determinar si existe una coincidencia isomorfa.

El método es similar en espíritu a cómo podrías resolver un sudoku. Hay algunos cuadrados cuyos valores potenciales están limitados por lo que ya sabes (el núcleo del espacio de la matriz), lo que te permite completarlos rápidamente. Luego, hay otras (la capa exterior) que tienen menos restricciones, pero que puede resolver simplemente probando todos los valores posibles, y mientras no haya demasiados de este tipo de cuadrados, aún puede resolver el rompecabezas en una cantidad razonable de tiempo.

“Completo todas las cosas que puedo decir rápidamente que son restringibles, y ahora podría volver y probar con todo mi corazón las casillas que faltan”, dijo Wilson. "Si ha reducido el alcance, ahora es un buen momento para cambiar de marcha y usar la computadora para buscar los valores correctos".

El avance de Sun estaba demostrando que siempre es posible hacer esta división para los espacios de matriz correspondientes a p-grupos de clase 2 y exponente p. Luego demostró que después de tal división, una combinación de técnicas algorítmicas hace posible determinar si dos espacios son isomorfos en $latex n^{{(log,n)}^{5/6}}$ time, un valor que es ligeramente menor que el método $latex n^{{(log,n)}}$ de Tarjan. (Ambos algoritmos también incluyen términos constantes, que no tienen un gran efecto en el tiempo de ejecución y que hemos omitido para mayor claridad).

El resultado no determina en qué categoría de velocidad cae el isomorfismo del grupo; todavía está en algún lugar entre tiempo exponencial y polinomial. Pero Sun lo ha empujado un poco más cerca del lado polinomial de las cosas, y hay razones para creer que más que eso debería ser posible. Después de todo, su trabajo proporciona a los informáticos un algoritmo de isomorfismo de grupo más rápido para los tipos de grupos más difíciles, lo que plantea la posibilidad de que una aceleración similar pueda estar al alcance de grupos de todo tipo.

“Si puedes resolverlo por p-grupos, probablemente puedan resolverlo todo”, dijo Grochow. "Tal vez."