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