TR04-008 Authors: Vikraman Arvind, Jacobo Toran

Publication: 22nd January 2004 21:35

Downloads: 1477

Keywords:

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}$.