0
$\begingroup$

Given a group G of order n and a subset S of G such that |S|=m.

What is the best algorithm for generating all the subgroups of G that contain S? How the complextity of such algorithm depends on n and m? Does it become easyer if G is a symmetric group?

  • 0
    I guess that finding the smallest subgroup contaning $S$ will be a good start2012-08-07
  • 0
    I can not come up with a better idea for doing that than calculating all the possible multiplications of elements from **S**. What I really need is a proof that there is no polynomial time algorithm that will solve the above problem.2012-08-07
  • 0
    Then give some context, where does this question comes from ?2012-08-07
  • 0
    I think that if you take $S={{e}},G=S_n$ there are exponential number of subgroups and so an optimal algorithm can't be polynomial2012-08-07
  • 0
    The problem comes from the following: I pick a subgroup of a symmetric group. You should guess, what subgroup did I pick by asking questions like: does the permutation **a** in your subgroup? You loose at your first question that has a negative answer. In case of positive answers you need to check only the subgroups that contain the elements you successfully checked. In my turn I should pick a subgroup in such a way to make it difficult for you to guess it.2012-08-07
  • 1
    @jack: Do you know to work with GAP?2012-08-07
  • 0
    @BabakSorouh: no I don't2012-08-07
  • 0
    Interestingly, there is no such algorithm for general infinite groups! As in, if you give me an element $g\in G$ and a subgroup $H\leq G$ it is in general undecidable if $g\in H$. The canonical example is taking $G=F_2\times F_2$. See [here](http://mathoverflow.net/questions/54335/showing-the-subgroup-membership-problem-is-undecidable-for-f-2-times-f-2).2012-08-07
  • 1
    How does the guesser ever win? If his only move is to guess elements, then he can only stalemate (just choose the identity element over and over). When you answer, think about how the game will work for G of order 2. Is there any strategy for the guesser (no matter how computationally expensive) that is better than "guess once completely randomly"?2012-08-07
  • 0
    @JackSchmidt: The guesser wins the game after guessing $k$ different elements consecutively. Let he guessed the elements $a_{1},...,a_{l}$ (possibly by random choice) and let my subgroup is of order $m$ and $G$ is of order $n$ than in case of completely random choice in the step $l+1$ he will guess with probability $(m-l)/(n-l)$ but if he can find and discard the set of elements $R$ that can not appear with $a_{1},...,a_{l}$ in any subgroup of G (assuming I did not pick G as a subgroup) then his random choice will give him higher probability of success: $(m-l)/(n-l-|R|)$2012-08-08

1 Answers 1