Dear Gap forum.

I am interested in the computational complexity of the GAP-function

PermGroupOps.SubgroupProperty.

Consider the call:

PermGroupOps.SubgroupProperty(G, P);

where G is some permutation group and P:G->Bool is some property. If every
element in G satisfies P, it seems to me like this function call terminates
very quickly - even when G is large. Is this observation correct and can it
be justified be referring to some general property of the backtrack
algorithm? (I assume that PermGroupOps.SubgroupProperty is the
GAP-implementation of the backtrack algorithm described, e.g., in Butler's
book "Fundamental Algorithms for Permutation Groups").

If G is the symmetrical group for some natural number n, I think I can
prove that the backtrack algorithm terminates after having tested exactly
n-1 permutations. Does this result generalize to all kinds of permutation
groups? Perhaps the number of permutations to test is equal to the number
of elements in the considered base for G?

I am definitely not an expert in the field of computational group theory
(or group theory for that matter), so it might be a quite well-known result
I am looking for.

Any help and/or references will be greatly appreciated.

Thanks,
Jens Baek Joergensen
Computer Science Department, Aarhus University
Ny Munkegade, Bldg. 540
DK-8000 Aarhus C
Denmark