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