ECCC-Report TR04-008https://eccc.weizmann.ac.il/report/2004/008Comments and Revisions published for TR04-008en-usThu, 22 Jan 2004 21:35:39 +0200
Paper TR04-008
| Solvable Group Isomorphism is (almost) in NP\cap coNP |
Vikraman Arvind,
Jacobo Toran
https://eccc.weizmann.ac.il/report/2004/008
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}$.
Thu, 22 Jan 2004 21:35:39 +0200https://eccc.weizmann.ac.il/report/2004/008