Rich (et al), Thanks for the lucid clarification (& lurid classification?<;-) of the hard "non-canonical group isomorphism" problem vs. related other ones! I do seem to have glommed onto a somewhat different question, which appears fun in its own right:
Checking a candidate isomorphism is, indeed, O(N^2), maybe less... How much work to check an isomorphism given as a table between two known-to-be groups given as tables [is] also interesting.
This is what got me curious: exactly how much less? For some reason I'd blithely assumed that the two groups were given in a canonical form (eg maybe they got generated that way?) and that the cost was being measured at the granularity of element operations, rather than whole-group black boxes (indeed, if G/ is just O(1) then G==H ought to be pretty trivial!) In case someone else finds this interesting, let me try to restate it clearly: Given *canonically represented* groups (eg as lexicographically-least tables?): 1. How fast can one be uniquely identified? 2. How fast can two be compared for equality? (where costs are measured in element operations). While not as hard as the non-canonical problem, just comparing canonical representations the size of the Monster, say, isn't exactly trivial. And even for small N, rapidly identifying, for example, which one of those fourteen order-16 groups we were discussing sounds handy. Moreover, using fancy "global" properties, such as Rich originally cited, might very well be less effective than something based on "local" element hacking. Consider string comparison, where you can return false after comparing the first elements, and returning true requires comparing all of the elements. Contrast this with comparing canonical group representations, where you can certainly ignore the 1 row/column, and you probably don't need to compare anywhere near N^2 elements. For example, you can distinguish A4 and Z4 just by comparing the canonical 2,2 element. What strategy will most efficiently distinguish any canonical pair of order N? What procedure will most efficiently identify any canonical GN? Etc.