Information Technology Reference
In-Depth Information
Thus as far as group representability is concerned, as long as we restrict the
problem to solvable groups, we are within the realm of graph isomorphism. However,
even for the simplest of the non-solvable case we do not have a satisfactory answer:
Open problem 7.8
(
A
5
representability problem) Given a graph
X
decide
whether there is a subgroup of Aut
(
X
)
which is isomorphic to the alternating group
of
A
5
.
The importance of
A
5
here is that it is the smallest example of a non-solvable
group. Since
A
5
is a simple group, non-trivial homomorphisms from it to Aut
(
X
)
can only be injections.
Torán [
Tor04
] showed that graph isomorphism is hard for a lot of parallel com-
plexity classes like
L etc. An important open problem in the context of graph
isomorphism is whether it is hard for the complexity class
P
(under suitable reduc-
tions). If this is the case, it would give evidence that it is unlikely to have efficient
parallel algorithms for graph isomorphism. We would like to pose the same question
for the group representability problem
≥
Open problem 7.9
Is the group representability problem hard for the complexity
class P.
Are there reasons to believe that the group representability problem is harder
than graph isomorphism? We really do not know. However, for the restricted case
of representability on trees, we already have a difficulty. Graph isomorphism on
trees can be done in polynomial time. In fact, even for planar graphs isomorphism
testing can be done in linear time [
HW74
] or, if one is interested in the space-bounded
classes, in logarithmic space [
DLNTW09
]. In contrast, [
DK09
] proved the following
result for representability on trees.
Theorem 7.10
(Dutta and Kurur)
The problem of group representability on trees is
Turing equivalent to the problem of testing, given an integer n in unary and group
G via multiplication table, whether there is a non-trivial homomorphism to the
symmetric group S
n
or not.
We call the problem of checking whether a group
G
has a homomorphism to
S
n
as
permutation representability problem
and is motivated by Cayley's theorem that
states that every finite group is a subgroup of a symmetric group. However, finding
the smallest
n
for which
G
is a subgroup seems to be hard although we admit that
there are no known hardness result for the above problem.
11.8 Conclusion
In this article, we discussed the complexity of some permutation group algorithms
and its close connection to graph isomorphism. Most of these algorithms perform a
divide and conquer and it is here the structure of permutation groups plays a crucial
role. Of particular interest are permutation group theoretic structures like orbits and
