Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Consider the next decision problem:
Given two finite groups represented by their multiplicity table, determine if they are isomorphic or not.
Clearly, this problem belongs to NP since given a witness in the form of an isomorphism between the groups it can be verified in polynomial time (to the input size). But what more can be said about this problem in terms of complexity?

share|improve this question
5  
    
Interesting. Thank you. –  Ido Aug 12 '12 at 21:06
    
Good question. I'd be interested to know more about the hardest case: p-groups. –  user641 Aug 12 '12 at 22:53
    
Also, are things easier when the groups are permutation groups? –  user641 Aug 12 '12 at 22:54
add comment

1 Answer 1

up vote 3 down vote accepted

As Colin McQuillan mentions above, this is an excellent survey of the state of the art: http://rjlipton.wordpress.com/2011/10/08/an-annoying-open-problem/

share|improve this answer
    
When posting (almost verbatim) something that has already been posted as a comment by someone else, the common courtesy would be to at least mention the author of the comment and post as community wiki.. –  tomasz Aug 12 '12 at 21:05
    
@tomasz To be quite fair, the comment entirely escaped my attention while posting. I was quite surprised to see it had an earlier timestamp. –  Erick Wong Aug 12 '12 at 21:15
add comment

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.