On the computational complexity of the Abelian permutation group structure, membership and intersection problems (Q1106934): Difference between revisions

Considered are groups defined by a set of permutations of a carrier each given as a product of cycles, disjoint within that product. In addition the groups are assumed Abelian (and finite) - which imposes a severe restriction on the cycles, when overlapping. - Deriving the complete structure of a group defined in such a manner is a complex task. The proposed algorithm - used in a proof for obtaining a limit for the complexity, and being the main essence of the reviewed paper - tries to exploit the idea to derive a base (with its exponents) by splitting the group into a Cartesian product of disjoint factors, or at least more generally by finding a supergroup with such a splitting. Hopefully these factors are cyclic - or at least decomposable into a product of disjoint cyclic subgroups each with an easily derivable base element: The complexity then is the ``sum'' of the complexities for the factors and no longer of about the order of their product. The presented derivation relies heavily on earlier publications of the author. Its goal is: partitions of the carrier into orbits as much disjoint as possible, each one covering overlapping cycles of the definition, so that each cycle is covered by some orbit. Besides the derivation also the computation of the membership-relation, and intersection of permutation groups is considered. The respective algorithms given are dependent on the afore mentioned procedure. For all computations limits or estimates of the required machine operations are given. - Author's correction: line 2, pg. 214 ``... for fixed j'' read ``... for fixed i''.