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\geq 0 an NC^{k+1} reduction to GI can be transformed into an AC^k reduction to the same problem.