Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

Question Given two finite groups G and H of the same order N what are the algorithms and what is their complexity (in terms of N) to check is G isomorphic to H or not ? Is there polynomial in N algorithm ?

Details Assume groups are given in the form of Cayley tables, we know the identity elements and inverses are known to us.

The complexity can be measured as "worst case" or "average" (in some sense of averaging) - I am interested in both, but primarily in "worst case".

By complexity I mean the count of the number of operations, there are some details in definition but I think they will not affect the answer essentially.


Naive exponential time algorithm Just consider all possible set-theoretic bijections between G and H and for each bijection check whether Cayley table is the same or not. Number of bijections is N! so worst case complexity is exponential.


For abelian groups seems linear time (=O(N)) algorithm seems exists:


Related:

Algorithm to check is representation irreducible ? Algorithm to decompose the reducible one ?

How to compute all irreducible representations of a finite group ? (how GAP is doing this?)

Complexity of computing the minimum degree of a faithful linear representation of a finite group

Constructing inequivalent irreps of finite groups

Recovering representation from its character

share|improve this question
    
"Exponential" is sometimes used to mean 2 to a polynomial exponent and sometimes to mean 2 to a linear exponent. So there can be disagreement as to whether $N!$ (or equivalently $N^{\log N}$) counts as exponential. –  Andreas Blass Nov 4 '12 at 14:54
    
Don't you mean $e^{N \log N}$? –  Derek Holt Nov 4 '12 at 22:35
    
@Derek: Yes, I do. Too bad comments can't be edited. –  Andreas Blass Nov 5 '12 at 14:46

1 Answer 1

up vote 4 down vote accepted

It is unknown whether this problem is polynomial. It is at worst $O(N^{\log N})$. To see that, observe that the group can be generated by at most $\log N$ elements, a homomorphism is determined by the images of its generators, and deciding whether a specific collection of images defines an isomorphism is polynomial (and fast in practice using defining relations for the group).

The hardest examples are likely to be $p$-groups (of class 2 or more) with about $O(\log N)$ generators, and I would guess that there is no way of doing that that is significantly faster than $O(N^{\log N})$.

share|improve this answer
    
Thank you very much ! Do you mean that finding generators and relations is O(N) ? Are there some references? –  Alexander Chervov Nov 4 '12 at 11:02
    
It can hardly be $O(N)$, because the multiplication table has $N^2$ entries. You can find generators with a single scan of the multiplication table. No serious algorithms use multiplication tables as input anyway! –  Derek Holt Nov 4 '12 at 12:37

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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