One-way functions and the nonisomorphism of NP-complete sets
Juris Hartmanis, Lane A. Hemachandra · Theoretical Computer Science · 1991
The One-way Conjecture states that the existence of nonisomorphic NP-complete sets implies the existence of one-way functions. This paper gives a relativized counterexample to the conjecture by constructing a relativized world that has nonisomorphic NP-complete sets, but lacks one-way functions.