< ^ From:

> < ^ Subject:

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

> < [top]