3
$\begingroup$

(1) Is it known Group Isomorphism is in $\mathsf{coNP}$ and is the conjecture so? Is there a good reference for $\mathsf{coNP}$-ness in similar situations?

(2) Is subgroup isomorphism $\mathsf{NP\text-complete}$?

(3) Is there an explicit relation between group cardinality and number of generators and bit size of generators that is used in the presentation of the group? For instance if the group has cardinality $2^{\log^cn}$ is there a bound on size and number of generators?

$\endgroup$
  • 1
    $\begingroup$ Why "Group homomorphism" in the title? The question is just about Group Isomorphism... $\endgroup$ – Joshua Grochow Nov 15 '15 at 20:52
6
$\begingroup$

(1) In terms of structural complexity classes (as opposed to just upper bounds on deterministic time), for general Group Isomorphism, the known upper bounds are essentially the same as for Graph Isomorphism, namely $\mathsf{coAM} \cap \mathsf{SZK}$. However, Arvind and Toran showed that Solvable Group Isomorphism is in $\mathsf{NP} \cap \mathsf{coNP}$ under a relatively benign derandomization assumption (in particular, weaker than that currently needed to show Graph Isomorphism is in $\mathsf{coNP}$). Although this isn't general Group Isomorphism, as solvable groups are widely believed to contain the hardest cases of Group Isomorphism, this is "pretty close." As it is conjecture that $\mathsf{coAM} = \mathsf{coNP}$, it is also conjectured that Group Isomorphism is in $\mathsf{coNP}$. In the Cayley table model, many people believe that Group Isomorphism is even in $\mathsf{P}$.

(2) Subgroup Isomorphism in the Cayley table model is unlikely to be $\mathsf{NP}$-complete, as it has a quasi-polynomial time algorithm. Namely, $H$ has at most $\log_2|H|$ generators; try all possible mappings of these generators into $G$ to see if any gives an injection. This takes time $|G|^{\log_2|H| + O(1)}$.

(3) Every finite group has a generating set of size at most $\log_2|G|$ (simple exercise). For the rest of this part of the question, it really depends on how the group is presented. However, note that how the group is given as input - e.g. Cayley table, generating permutations, generating matrices, generators-and-relations, black-box - also has a significant effect on the complexity of the corresponding algorithms. It is known that there are $n^{\Theta(\log^2 n)}$ groups of order $\leq n$, so by counting, groups of order $\leq n$ in general need $\Theta(\log^3 n)$ bits to describe. It is an open question whether there is always a presentation with generators-and-relations of poly-logarithmic size.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy