On Monday 06 September 2010 19:55:00 Victor Miller wrote:
Suppose that you're given a finite group G via black-box. That is you're given its order, n. There's a black box which you can query by giving it a pair of indices between 1 and n and gives back the index of their product (and perhaps you're told that element, 1, say is the identity, and perhaps given an oracle for the inverse). What's the most efficient algorithm to identify the isomorphism class of the group, where the efficiency might be measured in how many queries you need to make?
Google brings up a paper by someone called Kavitha which purports (presumably correctly, but I haven't checked) to prove that you can tell in time O(n) - whether the group is abelian; - whether the group is nilpotent; - what the order of each element is; - if the group is known to be abelian, what abelian group it is. Presumably the general case is much more difficult. Supposedly it's known to be in NP n co-NP for solvable groups, and it can't be any harder than graph isomorphism. Oh, I just found a paper by one Francois Le Gall which says that there's an algorithm for the abelian group isomorphism problem that takes time O(sqrt(n) log(n)^O(1)). As Kavitha's paper points out, though, there's no way even to tell whether a group is abelian without taking time proportional to n, because the centre of a nonabelian group can be large so you can't distinguish an abelian group from a nonabelian group with large centre without lots of queries. (Le Gall's paper is about efficient *quantum* algorithms for the problem, for a very restricted class of nonabelian groups.) -- g