Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Paper:

TR04-008 | 27th November 2003 00:00

Solvable Group Isomorphism is (almost) in NP\cap coNP

RSS-Feed




TR04-008
Authors: Vikraman Arvind, Jacobo Toran
Publication: 22nd January 2004 21:35
Downloads: 1285
Keywords: 


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



ISSN 1433-8092 | Imprint