[GAP Forum] Complexity questions

Alastair Donaldson ally at dcs.gla.ac.uk
Mon Jan 22 14:22:44 GMT 2007


Hi all

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)
- IsomorphicSubgroups(G,H) (I know this one is pretty bad!)
- ActionHomomorphism (G,B,OnSets) (where B is a block system for G)
- NormalSubgroups(G)

(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?

Thanks

Alastair


More information about the Forum mailing list