Hope this doesn't end-up in the maillist.
(I certainly had to avoid magic words in at least the first
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
M.Garey, D.Johnson "Computers and Intractability"
(A Guide to the Theory of NP-Completeness), 1979 Bell Telephone Labs, New
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.