deogun@unocss..unl.edu (Stan Wileman) (11/11/89)
We have a group G and subsets S_{1},...,S_{k} with the property that
each element g of G may be represented uniquely in the form
g = x_{1} . x_{2} ... x_{k} with x_{i} in S_{i} (i = 1,...,k).
Now given any element g in G, we wish to find x_{i} such that
g = x_{1} . x_{2} ... x_{k} with x_{i} in S_{i}.
In other words, we wish to find the factorization of g with respect to
the factor sets S_{i}. If the S_{i} are coset representatives with respect
to a chain of subgroups (eg. stabilizers) then the problem is easy. However,
if the S_{i} are arbitratry sets then the problem seems to be very difficult.
Is anything known about the complexity of this problem or other related
problems? Is it known to be NP-Complete?
I would greatly appreciate any information that you may provide.
You could reply to me via electronic mail if possible. My e--mail
address is memon@fergvax.unl.edu.
Nasir Memon