Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Paper:

TR02-037 | 21st May 2002 00:00

Graph Isomorphism is in SPP

RSS-Feed




TR02-037
Authors: Vikraman Arvind, Piyush Kurur
Publication: 19th June 2002 02:19
Downloads: 1629
Keywords: 


Abstract:

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



ISSN 1433-8092 | Imprint