Alistair, I don't think there any are polynomial-time algorithms for this problem known. Indeed, such an algorithm would allow one to compute the automorphism group of a graph in polynomial time. (Consider G=S_k acting on the set of n=(k choose 2) pairs. A graph is just a subset X of the set of pairs, so the stabilizer of X in G is the automorphism group of the graph) In turn, this would allow a polynomial-time algorithm for graph isomorphism.
On the other hand, going to the general case, it is polynomial-time for fixed |X|. Hope this helps. Dima http://www.ntu.edu.sg/home/dima/ On 2/23/07 6:04 PM, "Alastair Donaldson" <[EMAIL PROTECTED]> wrote: > Dear Forum > > Given a group G acting on {1,...,n} and a subset X of {1,...n}, I understand > that the algorithm which GAP uses to compute the set-wise stabilizer of X in G > is not a polynomial time algorithm (even though it is often quite efficient). > > However, if I have a subgroup H of G, is it possible to answer the question > "is H the set stabilizer of X in G?" in polynomial time? > > For my specific application it is always the case that H is a subgroup of the > set stabilizer, and I want to know if it is actually the whole thing. > > Thanks, in advance > > Alastair Donaldson _______________________________________________ Forum mailing list [email protected] http://mail.gap-system.org/mailman/listinfo/forum
