< ^ From:

< ^ Subject:

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

> < [top]