Dear gap forum,

joyner.david wrote:
!
!
! >
! > 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.
!
! I think this is not true, if I understand your question correctly. (It
! depends on
! what parameter you're using to measure the speed of the algorithm.) In
! general,
! for a graph with N vertices the shortest path problem has an O(N^3) -
! time
! algorithm. See Gibbons, Algorithmic Graph Theory, Cambridge Univ Press,
! section 1.4, page 32. The Cayley graph of G has |G| vertices, of course,
! so this algorithm is polynomial in |G| but exponential in b.
! - David Joyner

Thanks for the clarification. What I meant is, if it is known to be
NP-complete to find the shortest word mapping one arbitrary element to
another of a finite permutation group in terms of the cardinality of the
generating set and the number of moved points. As the Cayley graph is most
often exponential in terms of these, standard graph theory algs. are non
polonomial.

thanks,

-- 

- Istvan

Istvan T. Hernadvolgyi | WEB:   http://www.csi.uottawa.ca/~istvan
istvan@csi.uottawa.ca  | home:               ( 613 ) - 237 - 0168 
istvan@ottawa.com      | office: MCD 214, Tel: 562-5800 ext: 6782

Former Department of Computer Science
School of Information Technology and Engineering
University of Ottawa
Ottawa, Ontario K1N 6N5, Canada