Solvable Group Isomorphism is (almost) in NP CoNP
V. Arvind, Jacobo Torán · Conference on Computational Complexity · 2004
The Group Isomorphism problem consists in decidingwhether two input groups G_1 and G_2 givenby their multiplication tables are isomorphic. Wefirst give a 2-round Arthur-Merlin protocol for theGroup Non-Isomorphism problem such that on inputgroups (G_1,G_2) of size n, Arthur uses O(log^6 n)random bits and Merlin uses O(log^2 n) nondeterministicbits. We derandomize this protocol for thecase of solvable groups showing the following tworesults:(a) We give a uniform NP machine for solvableGroup Non-Isomorphism, that works correctlyon all but 2^polylog(n) inputs of any length n.Furthermore, this NP machine is always correctwhen the input groups are nonisomorphic.The NP machine is obtained by an unconditionalderandomization of the AM protocol.(b) Under the assumption that EXP ? i.o.PSPACE we get a complete derandomization of the above AM protocol. Thus,EXP ? i.o.PSPACE implies that Group Isomorphismfor solvable groups is in NP ? coNP.