Graph isomorphism is in SPP
V. Arvind, Piyush P. Kurur · 2003
We show that graph isomorphism is in the complexity class SPP and hence it is in /spl oplus/P (in fact, it is in Mod/sub k/P for each k/spl ges/2). We derive this result as a corollary of a more general result: we show that a generic problem FIND-GROUP has an FP SPP algorithm. This general result has other consequences: for example, it follows that the hidden subgroup problem for permutation groups, studied in the context of quantum algorithms, has an FP/sup 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 Mod/sub k/P for each k>2.