ONE-WAY FUNCTIONS AND THE ISOMORPHISM CONJECTURE

The isomorphism conjecture is investigated for exponential-time and ot her complexity classes. If one-way functions exist, then we show that there are one-way functions such that A congruent-to (p)f(A), where A is a standard complete set for NP or E or NE. If one-way functions exi st, we also show that there are k-completely creative sets in NP with one-way productive functions but which are p-isomorphic to standard co mplete sets. We then present a type of one-way functions whose existen ce is equivalent to the failure of the isomorphism conjecture for E. F inally, we show that the isomorphism conjecture holds for E (NE) if an d only if it holds for EXP (NEXP).