Abstract:
The Group Isomorphism problem consists in deciding whether two input groups $G_1$ and $G_2$ given by their multiplication tables are isomorphic. We first give a 2-round Arthur-Merlin protocol for the Group Non-Isomorphism problem such that on input groups $(G_1,G_2)$ of size $n$, Arthur uses $O(\log^6 n)$ random bits and Merlin uses $O(\log^2 n)$ nondeterministic bits. We derandomize this protocol for the case of solvable groups showing the following two results: \begin{itemize} \item[(a)] When the input groups are solvable, we give a uniform NP machine for Group Non-Isomorphism, that works correctly on all but $2^{{\rm polylog}(n)}$ inputs of any length $n$. Furthermore, this NP machine is always correct when the input groups are nonisomorphic. The NP machine is obtained by an unconditional derandomization of the AM protocol, and the derandomization is done using the Goldreich and Wigderson method \cite{GW} of extracting randomness from the input. \item[(b)] Using the Nisan-Wigderson generator we get another derandomization of the above AM protocol under the assumption that $\EXP\not\subseteq \ioPSPACE$. Thus, $\EXP\not\subseteq\ioPSPACE$ implies that Group Isomorphism for solvable groups is in $\NP\cap\coNP$. \end{itemize} Finally, we use the above AM protocol to show that Group Isomorphism (for arbitrary groups) cannot be complete for the limited nondeterminism class $\NP(\log^2 n)$ unless the coNP-complete problem $\overline{\clique}$ has polynomial-size proofs that can be checked in subexponential time with a polynomial-size advice. We also show that the hardness of Group Isomorphism for the parameterized class W[1] would have a similar unlikely consequence for $\overline{\clique}$.