Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Revision(s):

Revision #4 to TR11-052 | 4th July 2012 01:14

On the Complexity of Group Isomorphism

RSS-Feed




Revision #4
Authors: Fabian Wagner
Accepted on: 4th July 2012 01:14
Downloads: 2811
Keywords: 


Abstract:

The group isomorphism problem consists in deciding whether two groups $G$ and $H$
given by their multiplication tables are isomorphic.
An algorithm for group isomorphism attributed to Tarjan runs in time $n^{\log n + O(1)}$, c.f. [Mil78].

Miller and Monk showed in [Mil79] that group isomorphism can be many-one reduced to
isomorphism testing for directed graphs.
For groups with $n$ elements, the graphs have valence at least $n$.
We introduce a different reduction for isomorphism testing,
where the valence of the graphs, say $X(G)$ and $X(H)$,
and the complexity of the isomorphism test
is closely related to the structure of the groups.

Let $\mathcal{G}$ be the class of groups
having a composition series
where composition factors of size at least $\log n / \log\log n$
come before the others.

The composition series isomorphism problem
is given two composition series $S$ for $G$ and $S'$ for $H$,
such that any subgroup of $G$ according to $S$ is mapped blockwise onto that of $H$ according to $S'$.
In the reduction onto graph isomorphism, we get graphs $X(G,S)$ and $X(H,S')$.
Then for $p$-groups we find such an isomorphism in time $n^{cp}$ and for
the more general class of $\mathcal{G}$-groups
in time $n^{c\log n / \log\log n}$ for a constant $c$.

We analyze the time complexity for three isomorphism testing algorithms
with respect to two parameters $\beta, \gamma$ which depend on the group structure.
With a combination of the algorithms we also can show that $\mathcal{G}$-group
isomorphism is in time $n^{c (\gamma + \log\beta + \log n / \log\log n)}$,
and $p$-group isomorphism is in time $n^{c(p + \gamma + \log \beta)}$
with $\beta, \gamma \leq \log_p n$.
Most recently,
D.~Rosenbaum improves in [Ros12] these bounds
to $n^{(1/2)\log n + O(1)}$ for $p$-groups and nilpotent groups,
and to $n^{(1/2)\log n + O(\log n / \log\log n)}$ for solvable groups.



Changes to previous version:

The construction process to generalize the bounds for composition series isomorphism to general groups in the previous revision was found to be not correct by D. Rosenbaum.


Revision #3 to TR11-052 | 9th June 2012 16:57

On the Complexity of Group Isomorphism





Revision #3
Authors: Fabian Wagner
Accepted on: 9th June 2012 16:57
Downloads: 3165
Keywords: 


Abstract:

The group isomorphism problem consists in deciding whether two groups $G$ and $H$
given by their multiplication tables are isomorphic.
An algorithm for group isomorphism attributed to Tarjan runs in time $n^{\log n + O(1)}$, c.f. [Mil78].

Miller and Monk showed in~[Mil79] that group isomorphism can be many-one reduced to
isomorphism testing for directed graphs.
For groups with $n$ elements, the graphs have valence at least $n$.
We introduce a different reduction for isomorphism testing,
where the valence of the graphs, say $X(G)$ and $X(H)$,
and the complexity of the isomorphism test
is closely related to the structure of the groups.

The \emph{composition series isomorphism problem}
is given two composition series $S$ for $G$ and $S'$ for $H$,
such that any subgroup of $G$ according to $S$ is mapped blockwise onto that of $H$ according to $S'$.
In the reduction onto graph isomorphism, we get graphs $X(G,S)$ and $X(H,S')$.
Then for $p$-groups we find such an isomorphism in time $n^{cp}$ and for
general groups in time $n^{c\log n / \log\log n}$, for a constant $c$.

As pointed out by D. Rosenbaum [Ros12],
there was an error in an earlier version of this work.
This affected the bound of composition series isomorphism for general groups,
and remained correct for $p$-groups.
Therefore, we introduce a new processing step for general groups.

We analyze the time complexity for three isomorphism testing algorithms
with respect to two parameters $\beta, \gamma$ which depend on the group structure.
With a combination of the algorithms we also can show that group isomorphism is in
time $n^{c (\gamma + \log\beta + \log n / \log\log n)}$,
and $p$-group isomorphism is in time $n^{c(p + \gamma + \log \beta)}$
with $\beta, \gamma \leq \log_p n$.
Most recently, D.~Rosenbaum improves in~[Ros12] these bounds
to $n^{(1/2)\log n + O(1)}$ for $p$-groups and nilpotent groups,
and to $n^{(1/2)\log n + O(\log n / \log\log n)}$ for solvable groups.



Changes to previous version:

Corrections in abstract and the introduction.


Revision #2 to TR11-052 | 1st June 2012 00:46

On the Complexity of Group Isomorphism





Revision #2
Authors: Fabian Wagner
Accepted on: 1st June 2012 00:46
Downloads: 3394
Keywords: 


Abstract:

The group isomorphism problem consists in deciding whether two groups $G$ and $H$
given by their multiplication tables are isomorphic.
An algorithm for group isomorphism attributed to Tarjan runs in time $n^{\log n + O(1)}$, c.f.~[Mil78].

Miller and Monk showed in~[Mil79] that group isomorphism can be many-one reduced to
isomorphism testing for directed graphs.
For groups with $n$ elements, the graphs have valence at least $n$.
We introduce a different reduction for isomorphism testing,
where the valence of the graphs, say $X(G)$ and $X(H)$,
and the complexity of the isomorphism test
is closely related to the structure of the groups.

The \emph{composition series isomorphism problem}
is given two composition series $S$ for $G$ and $S'$ for $H$,
such that any subgroup of $G$ according to $S$ is mapped blockwise onto that of $H$ according to $S'$.
In the reduction onto graph isomorphism, we get graphs $X(G,S)$ and $X(H,S')$.
Then for $p$-groups we find such an isomorphism in time $n^{cp}$ and for
general groups in time $n^{c\log n / \log\log n}$, for a constant $c$.

We analyze the time complexity for three isomorphism testing algorithms
with respect to two parameters which depend on the group structure.
With a combination of the algorithms we also can show that $p$-group isomorphism is in
time $n^{c\log n / \log \log n}$.
D. Rosenbaum showed in~[Ros12] that this bound can be generalized to nilpotent groups.

As pointed out by D. Rosenbaum [Ros12],
there was an error in a previous version of this work.
This affected the bound of composition series isomorphism for general groups,
the bounds remained correct for composition series isomorphism
and group isomorphism for $p$-groups.



Changes to previous version:

A new processing step is introduced to apply the techniques used in a reduction to graph isomorphism for general groups.


Revision #1 to TR11-052 | 3rd July 2011 23:33

On the Complexity of Group Isomorphism





Revision #1
Authors: Fabian Wagner
Accepted on: 3rd July 2011 23:33
Downloads: 2980
Keywords: 


Abstract:

The group isomorphism problem consists in deciding whether two groups $G$ and $H$
given by their multiplication tables are isomorphic.
An algorithm for group isomorphism attributed to Tarjan runs in time $n^{\log n + O(1)}$, c.f. [Mil78].

Miller and Monk showed in [Mil79] that group isomorphism can be many-one reduced to
isomorphism testing for directed graphs.
For groups with $n$ elements, the graphs have valence at least $n$.
We introduce a different reduction embedded in isomorphism tests,
where the valence of the graphs, say $X(G)$ and $X(H)$,
and the complexity of the isomorphism test
is closely related to the structure of the groups.

When given additionally to the input a composition series $S$ for $G$ and $S'$ for $H$,
then in the reduction we get graphs $X(G,S), X(H,S')$ where
an isomorphism $\phi$ from $X(G,S)$ onto $X(H,S')$ gives an isomorphism $\phi'$ from $G$ onto $H$
such that $\phi'$ maps the subgroups in $S$ blockwise onto those in $S'$.
Then for $p$-groups, the reduction runs in time $n^{cp}$
and for general groups in time $n^{c\log n / \log\log n}$, for a constant $c$.

Conversely, finding such composition series for the groups,
i.e., such that there are isomorphisms that respect them,
is as hard as the group isomorphism problem.
We analyze the time complexity for three isomorphism testing algorithms
with respect to two parameters which depend on the group structure.



Changes to previous version:

There was an error in the previous version which affected the main result.
We consider now

- group isomorphism when given additionally composition series to the input groups,

- the time complexity of group isomorphism with respect to
two parameters which depend on the group structure.


Paper:

TR11-052 | 4th April 2011 14:28

On the Complexity of Group Isomorphism





TR11-052
Authors: Fabian Wagner
Publication: 11th April 2011 16:28
Downloads: 5655
Keywords: 


Abstract:

The group isomorphism problem consists in deciding whether two groups $G$ and $H$
given by their multiplication tables are isomorphic.
An algorithm for group isomorphism attributed to Tarjan runs in time $n^{\log n + O(1)}$, c.f. [Mil78].

Miller and Monk showed in [Mil79] that group isomorphism can be many-one reduced to
isomorphism testing for directed graphs.
For groups with $n$ elements, the graphs have valence at least $n$.
We many-one reduce group isomorphism onto graph isomorphism,
such that the valence of the graphs is at most $d+1$ if
$d$ is the size of the largest factor group in a composition series of the groups.
Combining this with the fact that isomorphism testing for graphs of valence $d$ can be solved in time $n^{O(d)}$,
$p$-group isomorphism is in time $n^{cp}$ for a constant $c$.

We extend this algorithm to work for general groups,
improving the exponential runtime behavior if factor groups of large size exist.
Then we also consider the following simple group isomorphism algorithm,
namely we compute a composition series and then guess coset representatives as generators.
This algorithm has the same worst-case behavior as Tarjans algorithm.
But if we combine both algorithms
then we can show that group isomorphism is in time $n^{c\log n / \log\log n}$ for a constant $c$.


Comment(s):

Comment #1 to TR11-052 | 26th April 2011 11:26

Error note

Authors: Fabian Wagner
Accepted on: 26th April 2011 11:26
Keywords: 


Comment:

As noted by L. Babai the proof of Lemma 4.9 is not correct because the composition series computed by Algorithm 1 do not satisfy the isomorphism properties stated in this lemma.
This affects the main result of the paper.


Comment #2 to TR11-052 | 1st June 2012 17:41

Error note

Authors: Fabian Wagner
Accepted on: 1st June 2012 17:41
Keywords: 


Comment:

D. Rosenbaum mentioned in arXiv:1205.0642
an error that affects the main result of the paper, such that Corollary 1.3 is true not for all groups.
It is correct e.g. for $p$-groups and an interesting
more general class of groups with given composition series $S$, where factor groups of size less than $\alpha$ come before the others in $S$.


Comment #3 to TR11-052 | 12th December 2013 08:47

Updated and improved version

Authors: Fabian Wagner
Accepted on: 12th December 2013 08:47
Keywords: 


Comment:

There is an updated and improved version
of the results for p-groups in arXiv:1205.0642 and TR11-052 in ECCC, see arXiv:1312.1755.




ISSN 1433-8092 | Imprint