12
$\begingroup$

In reading some blogs about computational complexity (for example here)I assimilated the notion that deciding if two groups are isomorphic is easier than testing two graphs for isomorphism. For example, on the stated page it says that graph isomorphism is a more general problem than group isomorphism.

Hence I am posing the following

Given a group $G$ can someone give a construction of a graph $\Gamma(G)$ of size polynomial in $|G|$ such that $$\Gamma(G) \cong \Gamma(H) \iff G \cong H$$ for groups $G$ and $H?$

$\endgroup$
  • $\begingroup$ while the two are tightly coupled as noted and researched for decades, afaict group isomorphism is not actually proved "easier" than graph isomorphism ie its roughly a major open question how their complexity is exactly related. also it would be helpful if you spelled out the math relationship in words also. $\endgroup$ – vzn Dec 30 '14 at 1:58
12
$\begingroup$

The reduction is described in a classic paper of Miller.

$\endgroup$
4
$\begingroup$

Not so fast. There is a big lurking ambiguity here:

How do you input your group for computation?

Unlike graphs, groups can be input be means that are far different in terms of input size and resulting complexity. The version cited in Miller is one of the least natural and for example you wont find that in a computer algebra system such as GAP, Magma, or Sage. So while it has a theoretical premise, it would be going too far to call that settling the problem.


  1. Generators and Relations: Group isomorphism is undecidable (graph isomorphism is decidable).

If history is the winner then the first mention of the Group Isomorphism problem was by Max Dehn in 1905. He assumed groups would be input by generators and relations. Adyan and Rabin in the 1950's proved that problem is undecideable. This situation occurs even if the group is trivial. So it is not just a cardinality issue. The key problem is you can create groups $G$ where to decide if $G=1$ would be to solve a rewriting problem that is non-primitive recursive. Similar to Halting type problems, it can't be done.

For groups input by generators and relations: group isomorphism is harder than graph isomorphism, in fact undecideable.

  1. Inputs used by software systems: group isomorphism of permutation and matrix groups is at least as hard as graph isomorphism (not the other way around).

This model of input assume groups are encoded in some natural way, say as permutations on a finite set, or as matrices over a ring or field. These are the methods introduced by Cannon and Neubuser in the first computer algebra systems in the 1960s which went on to be GAP and Magma. In this model you can embed the graph isomorphism problem into the group isomorphism problem. See for example work of Heinekin-Liebeck. It has since been carried out in other forms by others such as Sergeichuk. The key idea is to embed the adjacency matrix of a graph into the relations of a $p$-group.

For groups input for software systems: group isomorphism is at least as hard as graph isomorphism.

  1. Theoretical Complexity inputs: For a black-box group input, the group isomorphism is not known to be in NP or co-NP (graph isomorphism is in both).

This is a model for groups suggested by Babai-Szemeredi which assumes nothing about the input except that it be provided with (unit cost) functions for the group operations multiply, invert, test equality, and a set of generators. In their paper "On the complexity of matrix group problems" they discuss this problem and conclude its in $\Sigma^2$. The key problem is you cannot even define a certificate of isomorphism (thus it is not in NP) because you only have generators of the groups. So to provide an actual isomorphism $f:G\to H$ isn't possible, $G$ and $H$ are exponentially larger and from the generators alone you cannot know if $f$ is a valid homomorphism. At minimum you would seem to need a presentation of the groups, and that is not easily obtained.

For black-box groups: group isomorphism is at least as hard as graph isomorphism.

  1. Cayley table inputs.

Sometime in the 1970's Tarjan, Pultr-Hederlon, Miller and others observed that groups input by their entire multiplication table could also be treated as graphs. In this way group isomorphism does reduce to graph isomorphism in polynomial time. Miller went much further with this observing that numerous combinatorial structures do the same, Steiner triples for example. He also demonstrated that semigroup isomorphism is equivalent to graph isomorphism.

Recently Babai proved that Graph Isomorphism is in quasi polynomial time and the reductions now estimate a complexity of about $n^{O(\log n)}$, which is precisely the best known bound for group isomorphism for groups given by Cayley table. While no one has shown these two problems to be polynomial time equivalent, the presenting timings suggest a closer relationship than expected.

For Cayley tables: group isomorphism reduces to graph isomorphism.


Which input is the "right" group input? Well the Kolmogorov complexity of finite group of order $n$ is $O((\log n)^3)$ which is roughly the input sizes of the methods 1-3 above. Those input methods are natural and easily created, say by calculating generating permutations of a Rubiks cube or looking at generating loops of a fundamental group. So it makes sense that much of the theory and practice of group isomorphism use those models.

Yet while no computational algebra system uses Cayley tables, and most theoretical computer science uses structures like permutation groups, matrix groups, and black-box groups, there is still a good defense for the Cayley table perspective. In general the Kolmogorov complexity of structures such as semigroups is of order $n$ is $O(n^2 \log n)$ -- a theorem of Marshall Hall. And so you could not input semigroups any more concisely than by multiplication table. Therefore when you want to compare the complexity of group isomorphism to other natural structures (quasi-groups, loops, semigroups, etc) it makes sense to agree on a common input model.

$\endgroup$
  • $\begingroup$ Thanks for all the helpful discussion. One point: where you write "For groups input for software systems: group isomorphism is harder than graph isomorphism", do you have a citation for the claim that it is harder (rather than that it is at least as hard)? "Harder" would tend to imply that the complexities are not equal. Is there any evidence for that? Or did you actually mean "at least as hard"? $\endgroup$ – D.W. Sep 22 '18 at 6:04
  • $\begingroup$ Oops, shame on me, "at least as hard as" would be what is known. Strict inequality in complexity is as you say -- rare. However, one might observe that problems such as code equivalence (related to hypergraph isomorphism) is usually the problem one can reduce to from group isomorphism in these models. Code equivalence remains exponential complexity even after Babai's break through graph isomorphism in quasi-polynomial time. So that lends weak evidence for "harder", but no proof of strictly harder is known. I will correct the above. Thanks. $\endgroup$ – Algeboy Sep 22 '18 at 22:17

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.