ECCC-Report TR02-037https://eccc.weizmann.ac.il/report/2002/037Comments and Revisions published for TR02-037en-usWed, 19 Jun 2002 02:19:04 +0300
Paper TR02-037
| Graph Isomorphism is in SPP |
Vikraman Arvind,
Piyush Kurur
https://eccc.weizmann.ac.il/report/2002/037We 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$.
Wed, 19 Jun 2002 02:19:04 +0300https://eccc.weizmann.ac.il/report/2002/037