Name
Abstract | ||
|---|---|---|
We show that several reducibility notions coincide when applied to the Graph Isomorphism (GI) problem. In particular we show
that if a set is many-one logspace reducible to GI, then it is in fact many-one AC
0 reducible to GI. For the case of Turing reducibilities we show that for any k ≥ 0 an NC
k + 1 reduction to GI can be transformed into an AC
k
reduction to the same problem.
|
Year | DOI | Venue |
|---|---|---|
2007 | https://doi.org/10.1007/s00224-008-9159-1 | Theory of Computing Systems |
Keywords | Field | DocType |
Computational complexity,Reducibilities,Graph isomorphism | Graph canonization,Discrete mathematics,Combinatorics,Graph isomorphism,Reduction (recursion theory),Turing,Mathematics,Computational complexity theory | Journal |
Volume | Issue | ISSN |
47 | 1 | 1432-4350 |
ISBN | Citations | PageRank |
3-540-77049-6 | 0 | 0.34 |
References | Authors | |
10 | 1 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Jacobo Torán | 1 | 564 | 49.26 |