Re: [math-fun] distinguishing groups
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
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
On Thu, Sep 25, 2003 at 10:48:05AM -0400, John Conway wrote:
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.
But I thought this was exactly the graph isomorphism problem (which I incorrectly thought was NP-complete, but seems not to be known to be in P): given two graphs with k nodes, test if they are isomorphic in time polynomial in k. (In this case, k ~= log(N).) In this case, we are allowed to prepocess one of the graphs first; maybe that makes it easier. Peace, Dylan
On Thu, 25 Sep 2003, Dylan Thurston wrote:
That sort of problem is certainly there, but only for graphs of size log(N), so it shouldn't matter.
But I thought this was exactly the graph isomorphism problem (which I incorrectly thought was NP-complete, but seems not to be known to be in P): given two graphs with k nodes, test if they are isomorphic in time polynomial in k. (In this case, k ~= log(N).)
Yes, if indeed the graph isomorphism problem is there, this will show my expectation to be wrong, and I should have weakened the assertion to o(N) just in case. It does seem likely that it or a very similar problem is there, although I can't instantly see how to code it. [I was very keen to puff the methods we used in Cambridge, which in practice "always" work astonishingly well, but probably overstated the case. This feels very like the situation with graph automorphism, for which there are plenty of algorithms that in fact work very quickly, though we can't prove do so universally.] I've spoken too hastily more than once today. Sorry! JHC
participants (3)
-
Dan Hoey -
dpt＠exoskeleton.math.harvard.edu -
John Conway