The authors investigate separations and collapses in the power of reductions, in terms of their making sets complete for classes, and the stronger results implicit in certain types of completeness.

A long line of investigation, going back to Myhill’s Theorem from recursive function theory, which crossed into complexity theory via Berman and Hartmanis’s bold conjecture that all sets complete for NP with respect to many-one polynomial-time reductions are pairwise polynomial-time isomorphic, asks whether complete sets are necessarily isomorphic. This paper, building on earlier work by some of its authors that resolved the non-uniform analog [1], shows that all sets that are complete for NP with respect to P-uniform AC⁰ reductions are pairwise isomorphic, via mappings that are computable and invertible by depth-three P-uniform AC⁰ circuits. The paper shows that the “depth-three” cannot be replaced by “depth-two.”

With regard to separating completeness types, the paper shows that there exists a set that is complete for NP under Dlogtime-uniform AC⁰[mod2] reductions that is not complete for NP under non-uniform AC⁰ reductions, and notes that all the results just mentioned apply to a quite broad range of complexity classes. The paper is quite interesting, and in its final discussion section both lays out open issues, and provides late-breaking news.