On one-way functions and polynomial-time isomorphisms (Q1097694): Difference between revisions

Two sets A and B are polynomial-time isomorphic if there exists a polynomial-time computable, polynomial-time invertible, one-to-one correspondence f between the domains of the two problems such that \(x\in A\) iff f(x)\(\in B\) for all instances x. On the basis of the observation that all natural NP-complete sets are polynomial-time isomorphic, \textit{L. Berman} and \textit{J. Hartmanis} [SIAM J. Comput. 6, 305-322 (1977; Zbl 0356.68059)] conjectured that indeed all NP-complete sets are polynomial- time isomorphic. \textit{D. Joseph} and \textit{P. Young} [Theor. Comput. Sci. 39, 225-237 (1985; Zbl 0597.68042)] noticed that k-creative sets, a new class of NP-complete sets, do not seem to be polyomial-time isomorphic to natural NP-complete sets unless one-way functions do not exist. They conjectured that if one-way functions do not exist then not all NP- complete sets are polynomial-time isomorphic. The existence of one-way functions is, in this paper, related to the question of whether the EXP-complete sets are all polynomial-time isomorphic. It is known that the EXP-complete sets are equivalent under one-one, length-increasing polynomial-time reductions. Using the polynomial version of the Cantor-Schroeder-Bernstein construction, as described in Berman and Hartmanis, it follows that if one-way functions do not exist, then the EXP-complete sets are all polynomial-time isomorphic. It is proved in this paper that the existence of one-way functions is sufficient to distinguish, in the class EXP, between polynomial-time isomorphism and equivalence under one-one, length- increasing reductions. Furthermore, such sets can be made to be truth- table complete for EXP.