Reductions to Graph Isomorphism |
| |
Authors: | Jacobo Torán |
| |
Affiliation: | 1.Institut für Theoretische Informatik,Universit?t Ulm,Ulm,Germany |
| |
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 \(\textsf{AC}^{0}\) reducible to GI. For the case of Turing reducibilities we show that for any k≥0 an \(\textsf{NC}^{k+1}\) reduction to GI can be transformed into an \(\textsf{AC}^{k}\) reduction to the same problem. |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|