Abstract:
We show that all sets complete for NC$^1$ under AC$^0$ reductions are isomorphic under AC$^0$-computable isomorphisms. Although our proof does not generalize directly to other complexity classes, we do show that, for all complexity classes C closed under NC$^1$-computable many-one reductions, the sets complete for C under NC$^0$ reductions are all isomorphic under AC$^0$-computable isomorphisms. Our result showing that the complete degree for NC$^1$ collapses to an isomorphism type follows from a theorem showing that in NC$^1$, the complete degrees for AC$^0$ and NC$^0$ reducibility coincide.