On one-one polynomial time equivalence relations (Q1068536): Difference between revisions

Two sets A and B are said to be p-isomorphic (A\(\equiv B)\) if there is a bijection f such that f and \(f^{-1}\) are polynomial time one-one reductions from A to B and from B to A, respectively, and to be pseudo p- isomorphic \((A\equiv_ pB)\) if there are polynomial time length increasing one-one reductions from A to B and from B to A. \textit{L. Berman} and \textit{J. Hartmanis} [SIAM J. Comput. 6, 305-322 (1977; Zbl 0356.68059)] conjectured that all NP-complete (EXPTIME-complete or PTAPE- complete) sets are p-isomorphic, and showed that if \(A\equiv_ pB\) by invertible reductions then \(A\equiv B.\) In this paper it is proved that all EXPTIME-complete sets are pseudo p- isomorphic. So it follows that if the inverse of each length increasing polynomial time injection is polynomial time computable then all EXPTIME- complete sets are p-isomorphic. This result is also extended to many complexity classes, for example, k-SUBEXPTIME and DTAPE(S(n)), where \(k>0\) and S(n) is a tape constructible function with \(S(n)>p(n)\) for almost all n and for any polynomial p(n). In addition, this paper gives some nontrivial examples in EXPTIME-P which show the difference between one-one and many-one polynomial time equivalence relations.