informaticiens se rapprochent d'un objectif algorithmique majeur | Quanta Magazine

Si quelqu'un vous demande de déterminer si deux objets sont identiques, cela peut sembler une demande triviale. Dans la plupart des cas de la vie courante, un rapide coup d'œil vous suffit pour porter un jugement juste.

Mais en informatique, c'est une question beaucoup plus compliquée. En fait, c'est celui qui touche au cœur non résolu de ce dont les ordinateurs sont capables. Selon ce que sont les objets et comment vous définissez la similitude, nous ne savons toujours pas si les ordinateurs peuvent répondre rapidement à la question, ou si une approche lente et laborieuse est essentiellement la meilleure qu'ils puissent gérer.

Au cours de la dernière décennie, des résultats importants ont démontré que les ordinateurs peuvent faire au moins un peu mieux que cela. L'un des meilleurs résultats récents en informatique était un algorithme plus rapide pour déterminer quand deux graphiques sont identiques. Les travaux de 2015, par Laszlo Babai de l'Université de Chicago, a franchi une importante barrière de vitesse de calcul, mais n'en a pas réussi une autre.

Maintenant, un article de Xiaorui Soleil de l'Université de l'Illinois à Chicago a présenté un nouvel algorithme plus rapide pour une question connexe appelée problème d'isomorphisme de groupe, qui consiste à savoir quand deux objets mathématiques appelés groupes sont identiques. L'oeuvre, mise en ligne en mars dernier, fait un petit pas vers la clarification de la complexité de calcul sous-jacente impliquée dans la comparaison d'objets.

Le travail de Sun brise une limite de vitesse de longue date pour une classe particulière de groupes - celle considérée comme l'exemple le plus difficile du problème d'isomorphisme de groupe à résoudre. Si un algorithme peut rapidement comparer des groupes de ce type, l'espoir est qu'il puisse rapidement comparer des groupes de n'importe quel type.

"Nous ne connaissons pas un tel théorème, mais nous avons des raisons de croire que quelque chose comme ça devrait être vrai", a déclaré Josh Grochow de l'Université du Colorado, Boulder.

Comparer des comparaisons

Pour déterminer si deux choses sont identiques de manière précise, vous devez d'abord définir "la même chose". Deux chaînes de nombres peuvent être considérées comme identiques si elles contiennent simplement les mêmes chiffres, ou elles peuvent avoir besoin d'avoir les mêmes chiffres dans le même ordre.

L'isomorphisme est un type particulier de similarité qui revient souvent en mathématiques. Lorsque deux objets sont isomorphes l'un à l'autre, cela signifie en gros qu'ils contiennent les mêmes éléments et que ces éléments sont dans la même relation l'un avec l'autre.

Les graphes - des collections de sommets (points) reliés par des arêtes (lignes) - fournissent un moyen visuel et accessible de voir à quoi peut ressembler l'isomorphisme. Deux graphes sont isomorphes si vous pouvez faire correspondre les sommets d'un graphe avec les sommets de l'autre, de sorte que les sommets qui sont connectés par une arête dans le premier graphe sont connectés par une arête dans le second. Les graphes isomorphes peuvent sembler différents en surface, mais ils partagent une structure sous-jacente.

Les groupes sont plus abstraits que les graphes, mais ils se prêtent toujours à la comparaison par isomorphisme. Un groupe est une collection d'éléments - tels que des nombres - qui peuvent être combinés les uns avec les autres selon une opération afin que le résultat soit également dans la collection. Par exemple, vous pouvez avoir un groupe dont les éléments sont les entiers — tous les nombres entiers positifs et négatifs, plus zéro — et dont l'opération est l'addition : ajoutez deux entiers, et le résultat est toujours un autre entier.

Deux groupes sont isomorphes si vous pouvez coupler chaque élément d'un groupe avec un élément de l'autre, de sorte que le résultat de l'opération sur deux éléments du premier groupe soit cohérent avec le résultat de l'opération sur les valeurs équivalentes de ces éléments dans le second groupe.

Voici un exemple simple de deux groupes, chacun avec deux éléments, qui sont isomorphes l'un à l'autre. Le premier groupe est composé des chiffres 0 et 1, et le second groupe est composé des lettres a et les b. Les deux groupes contiennent une opération pour combiner les éléments du groupe d'une manière spécifique, avec les résultats présentés dans les tableaux ci-dessous.

Les groupes sont isomorphes car 0 paires avec a, 1 paires avec b, et la relation structurelle produite par la combinaison d'éléments est la même dans les deux groupes.

"Nous disons que deux groupes sont isomorphes s'ils sont fondamentalement équivalents", a déclaré Sun.

Progrès déséquilibré

L'isomorphisme est un concept important en mathématiques - où les graphiques et les groupes sont largement présents - car il permet aux mathématiciens de regarder au-delà des différences superficielles et de se concentrer sur la manière dont les objets liés peuvent en fait être les mêmes. Mais c'est aussi fondamental en informatique ; les chercheurs recherchent non seulement des algorithmes qui déterminent si deux objets sont isomorphes, mais mesurent également la vitesse à laquelle ces algorithmes peuvent s'exécuter.

Cette mesure peut être délicate. La vitesse d'un algorithme est basée sur la façon dont son temps d'exécution change avec la taille des objets sur lesquels il travaille. Imaginez, par exemple, que vous ayez deux paires de groupes. Dans une paire, chaque groupe contient cinq éléments. Dans l'autre, chaque groupe contient 10 éléments.

Vous vous attendriez à ce qu'un algorithme prenne plus de temps pour déterminer si les groupes avec plus d'éléments sont isomorphes. Mais combien de temps encore ? Cela prendra-t-il deux fois plus de temps ? 5² plus long? 2⁵ plus long? Ces questions correspondent à d'importantes classifications larges de la vitesse algorithmique : elles peuvent s'exécuter en temps linéaire (ce qui signifie dans ce cas que cela prend deux fois plus de temps), en temps polynomial (5² plus long) et le temps exponentiel (2⁵ plus long).

Les informaticiens savent à quelle catégorie de vitesse appartiennent la plupart des questions informatiques, mais pas toutes.

"La plupart sont soit les plus faciles, soit les plus difficiles [kind of question], mais il existe encore plusieurs exceptions qui sont inconnues", a déclaré Sun. L'isomorphisme des graphes et des groupes fait partie de ces exceptions, ce qui les rend si attrayants à étudier.

Dans les 1970s, Robert Tarjan de l'Université de Princeton s'est rendu compte qu'il existe un algorithme qui peut déterminer si deux groupes sont isomorphes avec un temps d'exécution de $latex n^{{(log,n)}}$, où n est le nombre d'éléments dans chaque groupe. C'est ce qu'on appelle un algorithme en temps quasi-polynomial, et dans la hiérarchie des temps d'exécution, c'est mieux que le temps exponentiel (2ⁿ) mais pire que le temps polynomial (n²). C'est à peu près la même vitesse que l'algorithme d'isomorphisme des graphes de Babai, et c'est toujours le mieux que nous puissions faire pour les groupes près de 50 ans plus tard.

"Cela signifie en gros qu'il n'y a pas eu de progrès depuis un demi-siècle", a déclaré Sun.

Au moment du résultat de Tarjan, le problème d'isomorphisme de groupe était plus largement étudié que la version graphique. C'est inversé aujourd'hui, en partie parce que l'isomorphisme des graphes a suscité des innovations passionnantes tandis que l'isomorphisme des groupes est au point mort.

"Tous nos outils ont été très lents pendant des années, et il a été difficile d'exploiter ce que nous savons sur l'algèbre [des groupes]", a déclaré James Wilson de l'Université d'État du Colorado.

Mais malgré cette disparité en cours, les deux problèmes ont un lien plus profond que la similitude de leurs noms : Le problème d'isomorphisme de groupe (au moins dans cette formulation) se réduit au problème d'isomorphisme de graphe. Cela signifie que tout algorithme capable de résoudre le problème du graphe peut également résoudre le problème du groupe dans un laps de temps similaire. L'inverse n'est pas vrai - le progrès sur le groupe n'implique pas le progrès sur le graphique. Mais le manque d'avancées sur le problème de groupe a pesé sur les mathématiciens à la recherche de gains proportionnels sur le problème des graphes. Comment pouvez-vous accomplir une chose plus difficile si vous ne pouvez pas d'abord accomplir quelque chose qui est étroitement lié et qui semble encore plus facile ?

"En d'autres termes", a déclaré Sun, "afin d'améliorer encore l'isomorphisme des graphes, l'isomorphisme des groupes est un gros goulot d'étranglement."

Un problème transformé

Lorsque les progrès sur un problème stagnent aussi longtemps que pour l'isomorphisme de groupe, l'invention est généralement nécessaire pour se débloquer. "Lorsque vous avez une grande avance, cela devrait être une indication qu'il y a une nouvelle idée", a déclaré Grochow.

Le travail de Sun contient quelques idées qui impliquent de cibler un type de groupe important et de trouver un moyen astucieux de diviser ces groupes en morceaux afin de les comparer.

Les groupes pour lesquels l'algorithme de Sun fonctionne sont appelés p-groupes de classe 2 et exposant p. Ils sont similaires aux groupes dans lesquels le produit de deux éléments est un autre élément et le produit reste le même quel que soit l'ordre dans lequel vous les multipliez. Mais ce qui compte vraiment, c'est ce qu'ils représentent pour le problème global d'isomorphisme de groupe. Ces groupes ont une structure très simple, ce qui signifie qu'ils devraient être faciles à comparer. Mais malgré cette simplicité, les chercheurs n'avaient pas trouvé de moyen d'accélérer l'algorithme. Jusqu'à ce qu'ils le puissent, il semblait vain d'apporter des améliorations à la question générale de l'isomorphisme de groupe.

Sun a commencé par changer le cadre des groupes en matrices, des tableaux de nombres qui servent d'objets fondamentaux en algèbre linéaire. Cela a été possible grâce à un théorème des années 1930 appelé la correspondance de Baer, ​​qui transforme cette version de la question de l'isomorphisme de groupe en un problème parfaitement analogue sur les matrices. En particulier, Sun a travaillé avec des espaces matriciels, qui sont des collections de matrices avec une propriété spéciale : la combinaison (linéaire) de deux matrices quelconques dans l'espace est égale à une autre matrice dans l'espace.

En d'autres termes, ces espaces sont structurés un peu comme des groupes. Ainsi, au lieu d'essayer de comprendre quand deux groupes sont isomorphes, Sun pourrait simplement essayer de comprendre quand deux espaces matriciels sont isométriques - une notion d'isomorphisme des espaces matriciels qui correspond à celle des groupes.

Sun n'a pas été le premier chercheur à adopter cette approche, mais il a été le premier à introduire une étape supplémentaire : diviser un espace matriciel en deux parties. Une pièce est le noyau de l'espace, dans lequel toutes les matrices sont simples. L'autre pièce est l'espace entourant ce noyau, dans lequel toutes les matrices sont particulièrement complexes. Ce déplacement correspond à la division d'un groupe en sous-groupes qui ne contiennent qu'une partie des éléments totaux.

Sun a ensuite appliqué différentes méthodes algorithmiques à chacune de ces pièces. Le noyau a une structure simple, il a donc utilisé une caractérisation de la structure pour la représenter de manière plus organisée. La couche externe est plus complexe, il n'y a donc pas de moyen évidemment rapide de la comparer à une autre. Au lieu de cela, la méthode de Sun adopte une approche appelée individualisation et raffinement pour exclure la plupart des façons possibles de mapper une couche externe sur l'autre, puis utilise un ordinateur pour parcourir toutes les façons possibles restantes de déterminer si une correspondance isomorphe existe.

La méthode est similaire dans son esprit à la façon dont vous pourriez résoudre un puzzle sudoku. Il existe des carrés dont les valeurs potentielles sont limitées par ce que vous savez déjà (le cœur de l'espace matriciel), ce qui vous permet de les remplir rapidement. Ensuite, il y en a d'autres (la couche externe) qui ont moins de contraintes, mais que vous pouvez comprendre simplement en essayant toutes les valeurs possibles - et tant qu'il n'y a pas trop de ces types de carrés, vous pouvez toujours résoudre le puzzle dans un laps de temps raisonnable.

"Je remplis toutes les choses que je peux rapidement dire sont contraignantes, et maintenant je pourrais revenir en arrière et essayer mon cœur sur les cases manquantes", a déclaré Wilson. "Si vous avez réduit la portée, c'est maintenant le bon moment pour changer de vitesse et utiliser l'ordinateur pour rechercher les bonnes valeurs."

La percée de Sun montrait qu'il est toujours possible de faire cette division pour les espaces matriciels correspondant à p-groupes de classe 2 et exposant p. Il a ensuite prouvé qu'après un tel découpage, une combinaison de techniques algorithmiques permet de déterminer si deux espaces sont isomorphes en $latex n^{{(log,n)}^{5/6}}$ temps, une valeur qui est légèrement inférieur à la méthode $latex n^{{(log,n)}}$ de Tarjan. (Les deux algorithmes incluent également des termes constants, qui n'ont pas un grand effet sur le temps d'exécution, et que nous avons laissés de côté pour plus de clarté.)

Le résultat ne détermine pas à quel isomorphisme de groupe de catégorie de vitesse appartient ; c'est toujours quelque part entre le temps exponentiel et polynomial. Mais Sun l'a poussé un peu plus près du côté polynomial des choses, et il y a des raisons de croire que plus que cela devrait être possible. Après tout, son travail fournit aux informaticiens un algorithme d'isomorphisme de groupe plus rapide pour les types de groupes les plus difficiles, ce qui soulève la possibilité qu'une accélération similaire soit à la portée de groupes de toutes sortes.

"Si vous pouvez le résoudre pour p-des groupes, vous pouvez probablement résoudre le problème dans son ensemble », a déclaré Grochow. "Peut être."