TR02-037 Authors: Vikraman Arvind, Piyush Kurur

Publication: 19th June 2002 02:19

Downloads: 3896

Keywords:

We show that Graph Isomorphism is in the complexity class

SPP, and hence it is in $\ParityP$ (in fact, it is in $\ModkP$ for

each $k\geq 2$). We derive this result as a corollary of a more

general result: we show that a {\em generic problem} $\FINDGROUP$ has

an $\FP^{\SPP}$ algorithm.

This general result has other consequences: for example, it follows

that the {\em hidden subgroup problem} for permutation groups, studied

in the context of quantum algorithms, has an $\FP^{\SPP}$

algorithm. Also, some other algorithmic problems over permutation

groups known to be at least as hard as Graph Isomorphism (e.g. coset

intersection) are in $\SPP$, and thus in $\ModkP$ for $k\geq 2$.