Dear Gap forum.
I am interested in the computational complexity of the GAP-function
Consider the call:
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.
Jens Baek Joergensen
Computer Science Department, Aarhus University
Ny Munkegade, Bldg. 540
DK-8000 Aarhus C