Name
Abstract | ||
|---|---|---|
We show that Graph Isomorphism is in the complexity class SPP, and hence it is in ⊕P (in fact, in ModkP for each k ≥ 2). These inclusions for Graph Isomorphism were not known prior to membership in SPP. We derive this result as a corollary of a more general result: we show that a generic problem FIND-GROUP has an FPSPP 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 FPSPP 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 each k ≥ 2. |
Year | DOI | Venue |
|---|---|---|
2006 | 10.1016/j.ic.2006.02.002 | Information & Computation |
Keywords | Field | DocType |
graph isomorphism,coset intersection,generic problem,complexity class spp,permutation group,fpspp algorithm,p algorithm,algorithmic problem,general result,quantum algorithm,hidden subgroup problem,machinery,permutation groups,graph theory,computer science,testing,complexity class,quantum algorithms,artificial intelligence,computational complexity,polynomials | Graph theory,Complexity class,Discrete mathematics,Combinatorics,Graph isomorphism,Hidden subgroup problem,Permutation group,Quantum algorithm,Coset,Mathematics,Computational complexity theory | Journal |
Volume | Issue | ISSN |
204 | 5 | Information and Computation |
ISBN | Citations | PageRank |
0-7695-1822-2 | 35 | 1.65 |
References | Authors | |
25 | 2 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| V. Arvind | 1 | 122 | 12.03 |
| Piyush P. Kurur | 2 | 88 | 9.41 |