[GAP Forum] Set stabilizer

[Dmitrii Pasechnik]

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" <ally at dcs.gla.ac.uk> 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