Polynomial-time isomorphism of 1-L-complete sets

Abstract

Let C be any complexity class closed under log-lin reductions. We show that all sets complete for C under 1-L reductions are polynomial-time isomorphic to each other. We also generalize the result to reductions computed byfinite-crossing machines. As a corollary, we show that all sets complete for C under two-way DFA reductions are polynomial-time isomorphic to each other.