[GAP Forum] Complexity questions

[Steve Linton]

Dear GAP Forum,



On Mon, 22 Jan 2007 14:22:44 -0000
"Alastair Donaldson" <ally at dcs.gla.ac.uk> wrote with some complexity
questions. I have some partial answers:

> 
> I'd like to know the worst case complexity for a number of algorithms which GAP implements.  Can anyone direct me to a good reference, or provide answers?
> 
> - AllBlocks(G)

The time to find all minimal block systems is O(n^2 log*(n)) (where log* is
the inverse Ackerman function). There are nasty cases where the
number of non-minimal block systems is huge, though. For instance the regular
representation of the elementary abelian group of order 64 has 2823 block
systems.

> - IsomorphicSubgroups(G,H) (I know this one is pretty bad!)

A trivial bound is |H|^rank(G) (rank G is size of shortest generating set of
G). I don't know if anything better can be said in general.

> - ActionHomomorphism (G,B,OnSets) (where B is a block system for G)

This takes essentially no time (maybe O(n)). Computing the image of an element
of G under the homomorphism takes O(|B|). 

> - NormalSubgroups(G)
> 

Again the elementary abelian group is a bad case with huge numbers of normal
subgroups. I don't know if anything sensible can be said in other cases.

> (where G is a finite permutation group and H<=G)
> 
> Also (not really a GAP question, I know) -- is there a worst-case result on how many distinct block systems a transitive group admits, given that G has degree n?
> 

The elementary abelian group of order 2^r acting on 2^r points has a block
system for every proper subspace of GF(2)^r. This is sequence A006116 in the
On-line encyclopedia of integer sequences. I don't have a formula for the
growth, but it's faster than exponential.

	Steve



-- 
Steve Linton	School of Computer Science  &
      Centre for Interdisciplinary Research in Computational Algebra
	     University of St Andrews 	 Tel   +44 (1334) 463269
http://www.cs.st-and.ac.uk/~sal 	 Fax   +44 (1334) 463278