Polynomial isomorphism of 1-L-complete sets
M. Agrawal, Somenath Biswas · 2002
Let C be any complexity class closed under log-lin reductions. It is shown that all complete sets for C under 1-L reductions are polynomial time isomorphic to one other. It is indicated how to generalize the result to reductions computed by finite-crossing machines.>