Path: utzoo!utgpu!news-server.csri.toronto.edu!cs.utexas.edu!usc!wuarchive!julius.cs.uiuc.edu!ux1.cso.uiuc.edu!sunb6!gooley
From: gooley@sunb6 (Markian "Party Mineral" Gooley)
Newsgroups: comp.theory
Subject: Heuristic for minimum-length generator sequence?
Message-ID: <1990Sep13.175713.9535@ux1.cso.uiuc.edu>
Date: 13 Sep 90 17:57:13 GMT
Sender: news@ux1.cso.uiuc.edu (News)
Reply-To: gooley@sunb4.cs.uiuc.edu (Mark. "Party Mineral" Gooley)
Organization: University of Illinois, Dept. of Comp. Science, Urbana
Lines: 11

[Reposted from sci.math]

"Given a set of generators of a permutation group G and a target permutation
P, find a shortest generator sequence realizing P."

Okay, this is well known to be NP-hard.  Are there any good heuristics for
solving instances of it?  What about for special cases -- say if G is
nonabelian, or simple, or (say) the alternating group of order n?

Mark.
gooley@cs.uiuc.edu