On Wed, 24 Sep 2003, Marc LeBrun wrote:
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.
In fact, as a practical problem, if you had a putative Monster (say) given as a set of generator names and a black-box multiplier, it's not at all hard to say whether it is or isn't the Monster. We used to do such things routinely when I was in Cambridge (we never actually did the Monster that way, but only because we didn't have the black-box multiplier, which has since become available). My feeling is that the methods we used could be converted into a formal proof that one could distinguish between any two given candidate groups of orders < N in a time bounded by some power of log N. [Note that that's weaker than saying "find which group of order < N you have".] John Conway