Dylan Thurston wrote:

On Tue, Sep 23, 2003 at 11:43:33AM -0700, Richard Schroeppel wrote:

...

Similar questions exist for graphs & other math objects.

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.

No, it isn't (unless I've missed a very surprising very recent breakthrough). It's a long-standing open problem. Because the graph isomorphism algorithms of unproven polynomiality are so good, it's conjectured that graph isomorphism is strictly easier than NP-complete (by people who are willing to conjecture that NP > P). Some people even conjecture it's P (even without conjecturing NP = P). You may be thinking of subgraph isomorphism, which is NPC, but there the hard part is finding the subgraph, not the isomorphism. (In the usual proof, the test graph is a complete graph, for which isomorphism is easy.

Is there a way of stating a finite-group-isomorphism problem so that it is decideable? Is it then NP-complete?

If you're given the multiplication table, it's certainly decidable. I suspect it's more likely to be polynomially related to graph isomorphism than NP-complete (but I haven't really worked on it). Dan