ECCC-Report TR11-052https://eccc.weizmann.ac.il/report/2011/052Comments and Revisions published for TR11-052en-usThu, 12 Dec 2013 08:47:40 +0200
Comment 3
| Updated and improved version |
Fabian Wagner
https://eccc.weizmann.ac.il/report/2011/052#comment3There 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.Thu, 12 Dec 2013 08:47:40 +0200https://eccc.weizmann.ac.il/report/2011/052#comment3
Revision 4
| On the Complexity of Group Isomorphism |
Fabian Wagner
https://eccc.weizmann.ac.il/report/2011/052#revision4The 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.Wed, 04 Jul 2012 01:14:24 +0300https://eccc.weizmann.ac.il/report/2011/052#revision4
Revision 3
| On the Complexity of Group Isomorphism |
Fabian Wagner
https://eccc.weizmann.ac.il/report/2011/052#revision3The 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.Sat, 09 Jun 2012 16:57:34 +0300https://eccc.weizmann.ac.il/report/2011/052#revision3
Comment 2
| Error note |
Fabian Wagner
https://eccc.weizmann.ac.il/report/2011/052#comment2D. 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$.Fri, 01 Jun 2012 17:41:53 +0300https://eccc.weizmann.ac.il/report/2011/052#comment2
Revision 2
| On the Complexity of Group Isomorphism |
Fabian Wagner
https://eccc.weizmann.ac.il/report/2011/052#revision2The 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.Fri, 01 Jun 2012 00:46:27 +0300https://eccc.weizmann.ac.il/report/2011/052#revision2
Revision 1
| On the Complexity of Group Isomorphism |
Fabian Wagner
https://eccc.weizmann.ac.il/report/2011/052#revision1The 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.Sun, 03 Jul 2011 23:33:38 +0300https://eccc.weizmann.ac.il/report/2011/052#revision1
Comment 1
| Error note |
Fabian Wagner
https://eccc.weizmann.ac.il/report/2011/052#comment1As 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.Tue, 26 Apr 2011 11:26:49 +0300https://eccc.weizmann.ac.il/report/2011/052#comment1
Paper TR11-052
| On the Complexity of Group Isomorphism |
Fabian Wagner
https://eccc.weizmann.ac.il/report/2011/052The 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$.Mon, 11 Apr 2011 16:28:18 +0300https://eccc.weizmann.ac.il/report/2011/052