Complete Problems and Strong Polynomial Reducibilities
Karthik Ganesan, Steven Thomas Homer · SIAM Journal on Computing · 1992
A set A is m-reducible to a set B if and only if there is a polynomial-time computable function f such that for all x, $x \in A \Leftrightarrow f(x) \in B$. A set C is m-complete for a class S if $C \in S$ and all sets in S are m-reducible to C. One-reducibility and one-completeness can be defined by requiring f to be one–one. Two sets A and B are p-isomorphic if the function f can be taken one-to-one, onto, and polynomially invertible. In this paper it is shown that all the m-complete sets are one–one complete for ${\operatorname{DTIME}}(2^{\mathcal{O}(n)} )$, ${\operatorname{NTIME}}(2^{\mathcal{O}(n)} )$, and the class of recursively enumerable sets. Further, all the sets complete for ${\operatorname{NTIME}}(2^{\mathcal{O}(n)} )$ under 1–L (or two-way DFA) reductions are p-isomorphic. All the m-complete sets for ${\operatorname{DTIME}}(2^{\mathcal{O}(n)} )$ are p-isomorphic if and only if all the m-complete sets for DTIME($2^{{\text{poly}}} $) are p-isomorphic.