RCS> For finite groups, I can check isomorphism in time roughly N^(log2(N)). MLB> How's that? If you're given the groups in some reasonable form how can it take more than the N^2 required to completely compare them element-wise? Perhaps this time includes making the inputs presentable? I should speak more precisely: Given two finite groups, I can decide if they are isomorphic in time roughly N^(log2(N)). Actually, N^(2+log2(N)). The hard part is finding the isomorphism. Checking a candidate isomorphism is, indeed, O(N^2), maybe less. I'm assuming the groups are given as lists of the elements, perhaps named G0, G1, ... and H0, H1, ..., and that there are black boxes G*, G/, H*, and H/ that provide products and reciprocals in time 1. I'm also assuming that the objects are indeed groups, although that could be checked in O(N^3) (or maybe less?). To search for the isomorphism I, you begin by developing a list of generators for G. First, scan the elements of G to locate the identity Gi so you can ignore it. We maintain of list of elements of G that we've already generated, and their formulas. This list starts with {Gi}. Then build a list of generators one at a time. Take the first element of G that isn't in the already-generated list, and call it a new generator. Expand the generated list with the new generator, closing under G*. (Don't need to bother with G/, it's a finite group.) Each new generator at least doubles the size of the generated set, so the total number of generators is <= log2(N). In the case of the group (Z2)^K, the formula is exact. Now that we have a list Ga,Gb,... of generators for G, we start searching for an isomorphism with H. We guess I(Ga) = Hx, and calculate the portion of I generated by Ga->Hx. For those that are consistent, we continue with a guess for Gb->Hy, and so on. I guess this comes out to N ^ (2 + log2(N)) if we include the time to check each candidate I. If we were actually making a list of all automorphisms of (Z2)^K, it's nearly N^(log2(N)). The separate puzzles, How much work to check a group given as a table is really a group? and How much work to check an isomorphism given as a table between two known-to-be groups given as tables? are also interesting. Obvious upper bounds are N^3 and N^2, but maybe we can do better. Rich rcs@cs.arizona.edu