On Tue, Sep 23, 2003 at 11:43:33AM -0700, Richard Schroeppel wrote:
Similar questions exist for graphs & other math objects.
DPT>The graph isomorphism problem is known to be NP-complete, so any sort of properties that distinguish graphs is likely to be hard to compute. Is there a way of stating a finite-group-isomorphism problem so that it is decideable? Is it then NP-complete? I think you're referring to Subgraph Isomorphism, Is the graph G isomorphic to any subgraph of H? which was one of the original bunch of NP-complete problems. AFAIK, the NP-completeness of the Graph Isomorphism Problem remains an open question. I think the approach I outlined for checking group isomorphism can be adapted to graphs, but some work is needed. When a vertex Gv is conjecturally mapped to Hv, it implies a "distance from Gv" stratification of G, which must match a similar stratification of H. In the ordinary case, choosing maps for log2(N) points from G to H will define the full isomorphism by intersecting stratifications. But there may be extraordinary graphs to consider. In my comments about finite groups, I assume the group was given as a table or some equivalent, which sidesteps the undecidable question, Is this particular set of generators and relations a finite group? "My" group isomorphism problem is clearly within NP (guess a map, check it in time N^2), but may NOT be NP-complete. Similarly, the group non-isomorphism problem seems to be of unknown hardness: We'd like to say G/=H implies there's some checkable property or feature of G and H that distinguishes them. But John has indicated we're out of luck for the time being. Rich rcs@cs.arizona.edu