Hope this doesn't end-up in the maillist.
(I certainly had to avoid magic words in at least the first
line.)

Hi everyone,

The other question I have is, if it is known to be NP-complete to find the
shortest word between two arbitrary elements in a permutation group for
a given generating set.

References are greatly appreciated.

I have no idea, but just in case: the reference that you might find
useful is:

M.Garey, D.Johnson "Computers and Intractability"
(A Guide to the Theory of NP-Completeness), 1979 Bell Telephone Labs, New
York.

This is a classic, so if you knew about it, sorry.

If not, then you might find your problem in their list,
or else browse it and try to prove NP-completeness yourself.
It's pretty short and they give quite a few hints.

- Istvan

Michael.

Miles-Receive-Header: reply