Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > KEYWORD > NONDETERMINISTICCLASSES:
Reports tagged with NondeterministicClasses:
TR04-008 | 27th November 2003
Vikraman Arvind, Jacobo Toran

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


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 ... more >>>




ISSN 1433-8092 | Imprint