0
$\begingroup$

I was searching for the graph isomorphism problem because I was looking for NP-COMPLETE problems to write about in a article I`m writing.

Learning about the problem a thing came to my mind, does this holds for groups to?

If I give a group A and a goup B and ask if there is a subgroup of B isomorphic to A, is this decision problem NP-COMPLETE?

If so, how do I prove it?

If not, why?

Improve this question
$\endgroup$
15
  • 3
    $\begingroup$ The triviality problem is undecidable for finitely presented torsion-free groups, so you can take $A=\mathbb{Z}$. This is a well known extension of the Adyan—Rabin theorem. $\endgroup$
    – HJRW
    Commented Jan 15, 2021 at 6:48
  • 1
    $\begingroup$ There are a bunch of problems in finite group theory, including centralizers of elements in subgroups of $S_n$, that are regarded as candidates for being strictly between P and NP. Normalizers in $S_n$ of subgroups might be NP-complete, but nothing has been proved. (Of course the problems have to be phrased as decision problems, like is the specified subgroup of $C_G(g)$ the whole of $C_G(g)$ for given $G \le S_n$.) $\endgroup$
    – Derek Holt
    Commented Jan 15, 2021 at 7:50
  • 4
    $\begingroup$ There is a lot of literature on complexity problems in finite group theory. Just do a search for complexity in group theory. Leading authors are Babai and Eugene Luks. In fact the proofs of Babai's recent ground-breaking work on the graph isomorphism theorem involve techniques for computing in subgroups of $S_n$. $\endgroup$
    – Derek Holt
    Commented Jan 15, 2021 at 8:46
  • 3
    $\begingroup$ I'd suggest you edit the question to clarify what you are looking for (the comments are not the right place to amend a question). In particular it would be useful to be specific about the input (a group is not an input, but rather a finite presentation). $\endgroup$
    – YCor
    Commented Jan 15, 2021 at 10:51
  • 5
    $\begingroup$ On that theme, for finite groups there are a number of different options for input. In practice, generators of the group (as permutations or matrices) tend to be the preferred option, but for some problems, including group isomorphism, even with input via group multiplication table, it is unknown whether there are polynomial-time solutions. $\endgroup$
    – Derek Holt
    Commented Jan 15, 2021 at 11:08

0

Reset to default

You must log in to answer this question.

Browse other questions tagged .