Are there any known NP-hard group theoretic problems?

Question

Are there any known NP-hard group theoretic problems which take as input finite groups given as Cayley tables (that is, not as a list of generators and product relations)?

I'm talking about abstract groups, not permutation groups. It seems that all known group theoretic problems that are hard seem to be variations of the word problem (in which case, the group is infinite) or computing distances between a permutation and a subgroup of the symmetric group (see Buchheim, Cameron, Wu https://webspace.maths.qmul.ac.uk/p.j.cameron/preprints/sd.pdf).

Answer 1

I don't believe so. The two main problems of interest in the Cayley table model are membership testing and isomorphism testing. Membership testing belongs to $\textsf{L}$ by reduction to path finding on an appropriate Cayley graph.

Isomorphism testing belongs to $\beta_{2}\textsf{L} \cap \beta_{2}\textsf{FOLL} \cap \beta_{2}\textsf{SC}^{2}$ by the generator enumeration strategy. Every group has a generating set of size at most $O(\log n)$ (and a cube generating set of size $O(\log n)$), and so we can guess a generating set with $O(\log^{2} n)$ bits and then perform marked isomorphism testing efficiently in parallel. The $\beta_{2}\textsf{FOLL}$ and $\beta_{2}\textsf{SC}^{2}$ bounds rely on guessing cube generating sequences.

It is known that $\beta_{2}\textsf{FOLL}$ cannot compute Parity. As Parity is $\textsf{AC}^{0}$-reducible to Graph Isomorphism, this shows that Group Isomorphism is strictly easier than Graph Isomorphism.

Furthermore, there is considerable evidence that Graph Isomorphism is not $\textsf{NP}$-complete. All of this evidence applies to Group Isomorphism as well.

• If GI is $\textsf{NP}$-complete, then the Polynomial-Hierarchy collapses to $\textsf{PH} = \Sigma_{2} \cap \Pi_{2} = \textsf{AM}$ (the last equality is again a consequence of the collapse and is not known to be true).
• GI is in the low hierarchy of $\textsf{NP}$. So GI is unlikely to be $\textsf{NP}$-complete, as again $\textsf{PH}$ would collapse (https://www.sciencedirect.com/science/article/pii/0022000088900104?via%3Dihub).
• GI is low for $\textsf{PP}$ and $\textsf{C=P}$. This is not known to be true for any $\textsf{NP}$-complete problem (https://link.springer.com/article/10.1007/BF01200427)
• If GI is $\textsf{NP}$-complete, then $\textsf{NP} \subseteq \textsf{DTIME}(n^{\text{poly} \log n})$, which implies that $\textsf{EXP} = \textsf{NEXP}$. It is widely believed that $\textsf{EXP} \neq \textsf{NEXP}$. (https://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.47.2228&rep=rep1&type=pdf)
• The decision and counting variants of GI are equivalent. This is not known to be the case for any $\textsf{NP}$-complete problem (https://www.sciencedirect.com/science/article/abs/pii/0020019079900048).

Also, Tensor Isomorphism problems in the multidimensional array (verbose) model have the same upper bounds as Graph Isomorphism. So even these much harder problems are unlikely to be NP-complete. (https://arxiv.org/pdf/1907.00309.pdf)