Polynomial-Time Isomorphism of 1-L-Complete Sets

摘要

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-crossingmachines. As a corollary, we show that all sets complete for C under two-way DFA reductions are polynomial-time isomorphic to each other.