Date: Wed, 24 Sep 2003 17:25:37 -0400 (EDT)
From: Dan Hoey <Hoey@aic.nrl.navy.mil>
To: John Conway <conway@math.princeton.edu>
Subject: Re: [math-fun] distinguishing groups
cc: math-fun <math-fun@mailman.xmission.com>

John Conway <conway@math.princeton.edu> wrote:

>     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".]

But it's the former problem that Rich is taking N^O(logN) to solve!
I suspect you're at least going to have to multiply that log N by
the sum of the orders of the generators, in case someone gave you
generators of two huge cyclic groups and asked you to test eqality
with the black box multiplier.

But even doing it in provably O(N^c) would be an advance.  I suspect
that's going to run into the same sort of problem graph isomorphism
has.  There are methods that work well on a lot of graphs, and
combining them _seems_ to work well on all graphs, but we can't prove
there isn't an exception.

Dan