Isomorphisme de groupe pour ismorphisme de graphe

En lisant certains blogs sur la complexité de calcul (par exemple ici ), j'ai assimilé la notion qu'il est plus facile de décider si deux groupes sont isomorphes que de tester deux graphiques pour l'isomorphisme. Par exemple, sur la page indiquée, il est dit que l'isomorphisme des graphes est un problème plus général que l'isomorphisme de groupe.

Par conséquent, je pose ce qui suit

Étant donné un groupe quelqu'un peut-il donner une construction d'un graphe Γ ( G ) de polynôme de taille dans | G | tel que Γ ( G ) ≅ Γ ( H $G$$\Gamma(G)$$|G|$ pour les groupes G et H

$$\Gamma(G) \cong \Gamma(H) \iff G \cong H$$ $G$$H?$

La réduction est décrite dans un article classique de Miller.

Pas si vite. Il y a une grande ambiguïté qui se cache ici:

Comment saisissez-vous votre groupe pour le calcul?

Contrairement aux graphiques, les groupes peuvent être entrés par des moyens très différents en termes de taille d'entrée et de complexité résultante. La version citée dans Miller est l'une des moins naturelles et par exemple, vous ne trouverez pas cela dans un système d'algèbre informatique tel que GAP, Magma ou Sage. Donc, même si elle a une prémisse théorique, ce serait aller trop loin pour appeler cela régler le problème.

1. Générateurs et relations: l'isomorphisme de groupe est indécidable (l'isomorphisme du graphique est décidable).

$G$$G=1$

Pour les groupes saisis par des générateurs et des relations: l'isomorphisme de groupe est plus difficile que l'isomorphisme de graphe, en fait indécidable.

2. Entrées utilisées par les systèmes logiciels: l'isomorphisme de groupe de permutation et les groupes matriciels sont au moins aussi difficiles que l'isomorphisme de graphe (et non l'inverse).

$p$

Pour les entrées de groupes pour les systèmes logiciels: l'isomorphisme de groupe est au moins aussi difficile que l'isomorphisme de graphe.

3. Entrées de complexité théorique: pour une entrée de groupe de boîte noire, l'isomorphisme de groupe n'est pas connu pour être en NP ou co-NP (l'isomorphisme du graphique est dans les deux).

$\Sigma^2$$f:G\to H$$G$$H$$f$est un homomorphisme valide. Au minimum, il semblerait que vous ayez besoin d'une présentation des groupes, ce qui n'est pas facile à obtenir.

Pour les groupes de boîtes noires: l'isomorphisme de groupe est au moins aussi dur que l'isomorphisme de graphe.

4. Entrées de table Cayley.

Dans les années 1970, Tarjan, Pultr-Hederlon, Miller et d'autres ont observé que les groupes entrés par l'ensemble de leur table de multiplication pouvaient également être traités comme des graphiques. De cette façon, l'isomorphisme de groupe se réduit à l'isomorphisme de graphe en temps polynomial. Miller est allé beaucoup plus loin en observant que de nombreuses structures combinatoires font de même, Steiner triple par exemple. Il a également démontré que l'isomorphisme semi-groupe est équivalent à l'isomorphisme graphique.

$n^{O(\log n)}$

Pour les tables de Cayley: l'isomorphisme de groupe se réduit à l'isomorphisme de graphe.

$n$$O((\log n)^3)$

$n$$O(n^2 \log n)$