^ From:

> ^ Subject:

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

> < [top]