On Wed, 24 Sep 2003, Dan Hoey wrote:
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 think he's actually doing more than that. But of course he's not using the powerful group-theoretical and computational tools that the Cambridge people did.
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.
I should have said that I'd have to know the factorizations of the orders of my two candidate groups. Then there's an easy algorithm by which the black-box multiplier can find the order of an element of either of them.
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.
That sort of problem is certainly there, but only for graphs of size log(N), so it shouldn't matter. John Conway